Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

For example, consider the following string of numbers:


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?

share|cite|improve this question

migrated from Nov 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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.