# Find the longest repeated pattern in a string

I'm looking for an efficient algorithm to find the longest repeated pattern in a string.

For example, consider the following string of numbers:

5431428571428571428571428571427623874534.

As you can see, 142857142857 is the longest pattern which is repeated for a couple of times (at least twice) in this string.

The repeated string should not contain any re any idea rather than brute-force?

-

## migrated from cstheory.stackexchange.comNov 20 '12 at 1:41

This question came from our site for theoretical computer scientists and researchers in related fields.

You did not define what “a couple of times” means, but if “twice” counts as “a couple of times,” then 142857 is not the longest because 142857142857 is longer. I think that you should edit the question to clarify what you mean by “repeated pattern.” – Tsuyoshi Ito Nov 8 '12 at 20:06
very good point. I will update the question. – MBZ Nov 8 '12 at 20:07
Are you requiring the occurrences of the pattern to be disjoint from each other? Because if not, 142857142857 is still not the longest repetition; 142857142857142857142 occurs twice. In any case, the usual answer to questions like this is "suffix trees". – David Eppstein Nov 8 '12 at 20:44

## 1 Answer

The problem is surprisingly non-trivial. First, two brute force algorithms. A square ("repeated pattern") is given by its length $\ell$ and position $p$, and takes time $O(\ell)$ to verify. If we go over all $\ell$ and $p$, we obtain an $O(n^3)$ algorithm. We can improve on that by first looping over $\ell$, and then scanning the string with two running pointers at a distance of $\ell$. In this way, one can verify whether a square of length $2\ell$ exists in linear time, giving a total running time of $O(n^2)$.

Kolpakov and Kucherov (Finding maximal repetitions in a word in linear time) developed an algorithm for finding all maximal repeats in a word in time $O(n)$, and their algorithm can be used to find all maximal squares in time $O(n)$. A repeat is a subword of the form $w^kx$, where $k \geq 2$ and $x$ is a proper prefix of $w$. The largest square contained in that repeat is $(w^{\lfloor k/2 \rfloor})^2$. Using this formula, given all maximal repeats in a word (of which there are only $O(n)$ many), one can find the largest square.

-