I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring of $x$.
What I mean is the following cases:
In "aa" I want "a" with a position of 0 and repetition of 2 In "aaab" I want "a" with a position of 0 and repetition of 3 In "abc" I want "" (false or whatever) In "abababc" I want "ab" with a position of 0 and repetition of 3 In "aaabbbb" I want "b" with a position of 3 and repetition of 4 In "eabcdabcde" I want "abcd" with a position of 1 and repetition of 2 In "cababcab" I want "ab" with a position of 1 and repetition of 2 (not 3, because of the "c" between the three "ab"'s)
I've been looking at various suffix and prefix algorithms, but none of them has the "no gaps" part build into it. Both LCP arrays and Suffix arrays seems to suffer from this.
Googling for "Longest repeated substrings" gives me algorithms which e.g. find
"abcdehellofghijhelloklmn", but this is not what I want.
ababababc, we would actually must more prefer to get
abab. So we are actually looking for the shortest sequence in a repeated sequence in a string. $\endgroup$