# Fastest way to find a substring 'ab' inside a string 'abab'

Let $$A$$ be an input alphabet - a finite set of symbols. Elements of $$A$$ are called the characters. The alphabet I am interested in is the set of all ordinary letters a, b, c, ..., z.

The texts (also called words or strings) over $$A$$ are sequences of elements of $$A$$. The length (size) of a text is the number of its elements (with repetitions). So, the length of aba is 3.

The $$i$$-th element of the word $$x$$ is denoted by $$x[i]$$ and the integer $$i$$ is its position in $$x$$. I denote by $$x[i\ldots j]$$ the subword $$x[i]x[i+1]\ldots x[j]$$ of $$x$$. If $$i\gt j$$, by convention, the word $$x[i\ldots j]$$ is the empty word (the sequence of length zero).

Given the word $$x$$ of length $$n$$ and the word $$y$$ of length $$m$$ the word $$xy$$ is defined as $$x[1]x[2]\ldots x[n]y[1]y[2]\ldots y[m]$$.

I say that the word $$x$$ of length $$n$$ is a factor of the word $$y$$ if $$x=y[i+1\ldots i+n]$$ for some integer $$i$$. I also say that $$x$$ occurs in $$y$$ at position $$i$$ or that the position $$i$$ is a match for $$x$$ in $$y$$.

A rotation of a word $$u$$ of length $$n$$ is any word of the form $$u[k+1\ldots n]u[1\ldots k]$$, denoted by $$u^{(k)}$$ (it holds that $$u^{(0)} = u^{(n)} = u$$).

I am interested in an algorithm that given as inputs a string $$x$$, a string $$y=xx$$ and a rotation $$z=y^{(k)}$$ returns as output the first occurence of $$x$$ in $$z$$.

The above definitions are quoted almost verbatim from the book: M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994, 412 pages. ISBN 0-19-508609-0. Courtesy of the author at http://monge.univ-mlv.fr/~mac/REC/B1.html

Some test cases: The inputs are baba and ab; the output is 2 because (starting index from 1) the first uninterrupted occurence of ab in baba is at index 2. An interrupted occurence of ab inside baba is at index 4.

Some more examples:

Input: abcabc,abc. Output: 1.

Input: cabcab,abc. Output: 2.

Input: bcabca,abc. Output: 3.

• You can use any linear time matching algorithm, for example KMP. Mar 10, 2020 at 13:03
• Please don't use "EDIT:" or keep around old, incorrect/obsolete material. We have revision history for people who want to see prior versions. Instead, please write the question so it reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755.
– D.W.
Mar 10, 2020 at 17:03