What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end? 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 &gt; 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 &gt;= 1 - len; substringI -= len) {

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

                // See how many characters match.
                if (sequence[substringI + charI] === sequence[suffixI + charI]) {
                    repeatLength++;
                    if (repeatLength &gt; 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.
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.