What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?

Question

Here are some sequences:

'0.66666'
[3,0,1,2,2,2,0,1]
'banana'
'bandana'
'11221122'

I would like to find the index and length of the substring in each which is repeated (even if partially) for the most terms and which repeats until the end.

I wrote a function in JavaScript that successfully returns the expected output:

'0.66666'           After occurring at index 2, '6' repeats for 4 terms.
[3,0,1,2,2,2,0,1]   After occurring at index 1, [0,1,2,2,2] repeats for 2 terms.
'banana'            After occurring at index 1, 'an' repeats for 3 terms.
'bandana'           After occurring at index 4, 'an' repeats for 1 terms.
'11221122'          After occurring at index 0, '1122' repeats for 4 terms.

Explanation:

• [3,0,1,2,2,2,0,1] is a sequence with 8 terms. [0,1,2,2,2] is the longest substring which repeats at least partially to the end of the sequence, because after its first occurrence it repeats directly after for another 2 terms. Then the sequence terminates.
• If we were to input [3,0,2,2,2,0], you might think the substring [2] wins because it repeats for 2 terms following its first occurrence, but it doesn't repeat to the end so the substring [0,2,2,2] wins as the term that follows the only occurrence of this substring (0) is also the first term in the substring meaning that it repeats for 1 term following the first occurance.

Repetition must continue to the end so for the second example [2,2,2] is not valid though it also repeats for two terms

Here's the function (JS Bin):

function longestRepeatedSuffix(sequence) {
    var repeatStart;
    var blockLength;
    var maxRepeatLength = 0;

    // Go through each suffix from length 1 to the length of the sequence - 1.
    suffixLoop: for (var suffixI = sequence.length - 1; suffixI > 0; suffixI--) {
        var len = sequence.length - suffixI;
        var repeatLength = 0;

        // Go right to left through adjacent substrings the length of suffix.
        // substringI may be negative on the last iteration.
        for (var substringI = suffixI - len; substringI >= 1 - len; substringI -= len) {

            // Go right to left through characters in the suffix and current substring.
            for (var charI = len - 1; charI >= 0 && substringI + charI >= 0; charI--) {

                // See how many characters match.
                if (sequence[substringI + charI] === sequence[suffixI + charI]) {
                    repeatLength++;
                    if (repeatLength > maxRepeatLength) {
                        maxRepeatLength = repeatLength;
                        repeatStart = substringI + charI;
                        blockLength = len;
                    }
                } else {
                    continue suffixLoop;
                }
            }
        }
    }
    return 'After occurring at index ' + repeatStart + ', "' +
        sequence.slice(repeatStart, repeatStart + blockLength) +
        '" repeats for ' + maxRepeatLength + ' terms.';
}

I believe this is an O(n^2) implementation even though I used 3 nested for-loops. So my question is: how can I use something like a suffix-tree to get even better time complexity?

Similar algorithm:

• Longest repeated substring: This is different, as it includes repetitions which overlap and those which are not adjacent (not just consecutive repetitions) and it doesn't require repetition to continue to the end.

Answer 1

This can be solved with a prefix function in linear time.

Prefix function of a string $S$ is an array $p$ of length $s$, where $p_i$ is the length of the longest border of a string $s_1 \dots s_i$. The $border$ of a string is its longest proper prefix which is also a suffix. E.g. the border of $abacaba$ is $aba$, the border of $ababa$ is $aba$, the border of $banana$ is empty. The prefix function can be computed in linear time (see this Coursera lecture, for example).

For simplicity I reverse the string and now look for a recurring prefix, not suffix. Let $p_i$ be the prefix function of the string. Then the length of the shortest recurring substring of the $i$-th prefix of the string is $i - p_i$:

s: a b a c a b a c a b a
p: 0 0 1 0 1 2 3 4 5 6 7
   -------------
           -------------
   + + + +

With hyphens I denote the matching prefix-suffix pair found by prefix function, and with pluses the generating prefix itself. It is easy to see that it ends exactly where the matching suffix begins, that is, at the position $i - p_i$.

Having the length, the answer is trivially computed as $i - (i - p_i) = p_i$. Isn't it the nice observation? ;) So what you actually want to do is to take the maximum value of the prefix function of the reversed string.

Answer 2

Let $x[1],\ldots,x[n]$ be your string and let the alphabet be $A=\{1,2,\ldots,m\}$. Do a single pass in $O(n)$ and determine the highest frequency character $a \in A$ and its support, so $S_a=\{i: 1\leq i\leq n, x[i]=a\}$ and $f_a=\# S_a.$

If I understood the question as being the "most common substring with partial repeats", you are looking for is the longest substring which starts at the first occurence of $a$, i.e., $k=\min(S_a)$ and its length is $$n-\min(S_a)+1.$

So the candidate string $C_a$ is $x[k],x[k+1],\ldots,x[n].$

You can find it in $O(n)$ time as above.

Edit: In response to OPs comment, let $k'=\max(S_a).$ One can now see if string $x[k'],\ldots,x[n]$ is a prefix of the candidate string $C_a$. Call this Condition 1. If yes, we are done. If no, repeat above algorithm for the next most frequent letter $a',$ etc. until we find that Condition 1 holds. This would seem to give $O(n^2)$ complexity.

Answer 3

This can be solved in $O(n)$ time, i.e., linear time, using a suffix tree or suffix array. Let $S[1..n]$ denote the input string. You want to find the largest length $\ell$ such that the suffix $S[n-\ell+1..n]$ appears somewhere in $S[1..n-\ell]$.

This can be solved with a suffix tree. Let $S^r$ be the reversal of $S$ (i.e., the string $S[n]S[n-1] \cdots S[1]$). Build a suffix tree/array for $S^r$. Given any string $t$, this lets you find the last place where $t$ appears as a substring of $S^r$, i.e., the first place where $t^r$ appears as a substring of $S$. Now there's a nice algorithm for your problem:

• Build a suffix tree for $S^r$.

• For $\ell := 1,2,\dots,n$:

  • Look up the string $S[n] S[n-1] \cdots S[n-\ell+1]$ in the suffix tree for $S^r$.

  • Use this to find the first (smallest) index $i$ in $S$ where the string $S[n-\ell+1..n]$ appears in $S$.

  • If $i \le n-2 \ell$, you've found a valid candidate substring that repeats for $\ell$ terms.

• Output the last candidate you found, i.e., for the largest value of $\ell$ where you found a valid candidate.

Note that if you keep track of where you are in the suffix tree for $S^r$, then each iteration of the loop can be done in $O(1)$ time. You can build a suffix tree for $S^r$ in linear time, too. Therefore, the total running time is $O(n)$.