0
$\begingroup$

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 "hello" in "abcdehellofghijhelloklmn", but this is not what I want.

Improve this question
$\endgroup$
3
  • $\begingroup$ Oh, I see. Anyway, a suffix tree holds all the information you need; the deepest inner nodes with children that have fitting indices. The question is how you augment the tree so that this property is easy to check for each node. $\endgroup$
    – Raphael ♦
    Apr 20, 2016 at 9:22
  • $\begingroup$ While discussing my problem with my colleagues, we found that some of the behavior of our wanted algorithm is unspecified. In the case of ababababc, we would actually must more prefer to get ab than abab. So we are actually looking for the shortest sequence in a repeated sequence in a string. $\endgroup$
    – Mads Ohm Larsen
    Apr 20, 2016 at 11:07
  • $\begingroup$ @MadsOhmLarsen Sure but any string that matches contains $y^n$ for $n\geq2$ also contains $yy$. $\endgroup$
    – David Richerby
    Apr 21, 2016 at 8:18

2 Answers 2

Reset to default
1
$\begingroup$

From what I understand you are looking for maximal substrings of the form $y^k$ for $k\ge 2$. By some this is called a repetition in a string. One of the first to give an algorithm for finding these is Maxime Crochemore: An optimal algorithm for computing all the repetitions in a word, Inform. Process. Lett. 12 (1981) 244-248. From what I understand his approach has been reformulated in terms of suffix trees and arrays.

Improve this answer
$\endgroup$
0
$\begingroup$

After fiddling a bit around with different options, we discovered, that what we really needed was as simple as the regular expression: (.+)\1+. This will match at least one character and then match at least one of the same match again.

Having aaab will then match the a which is present three times.

In cababcab, we match the first ab which is there twice and so on.

Sidenote: Now the next problem is implementing this for something other than strings and characters, e.g. C++ objects.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.