Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Nov 20 '12 at 1:41

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

3  
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
8  
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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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