2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I moved this question from Stack Overflow: stackoverflow.com/questions/44338562/… $\endgroup$ – Web_Designer Jun 2 '17 at 23:23
  • 1
    $\begingroup$ Why isn't the answer for bandana that a repeats 3 times? In one place you mention longest repeated substring. In other you mention you are looking for a substring that is repeated the most times. Those are two different problems. Which one are you dealing with? Also, what does it mean to "repeat until the end" or for "require repetition to continue to the end"? I don't understand what you mean by that. Please edit your question to clarify and make it internally self-consistent. $\endgroup$ – D.W. Jun 2 '17 at 23:46
  • $\begingroup$ In your example [3,0,1,2,2,2,0,1], why do you say that [0,1,2,2,2] repeats 2 times? I see only one copy of it in the input. What do you mean by "terms"? I am assuming "terms" means "times"; have I misunderstood? $\endgroup$ – D.W. Jun 2 '17 at 23:47
  • $\begingroup$ @D.W. [0,1,2,2,2] is a substring with 5 "terms" or characters. After the first occurrence of the substring, it is partially repeated for another 2 terms. $\endgroup$ – Web_Designer Jun 2 '17 at 23:49
  • $\begingroup$ I still don't see the answer to my previous questions. Can you give a more precise statement of the problem? A set of examples is not a substitute for a clear, general specification of the inputs and desired outputs. $\endgroup$ – D.W. Jun 2 '17 at 23:55
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would you mind explaining what the prefix function is? Is it a standard object? Is there a standard way to compute it? $\endgroup$ – D.W. Jun 5 '17 at 1:21
  • $\begingroup$ @D.W. Sorry, I was sure for my whole life that the wiki page on KMP does have the definition. I've added it to the post. $\endgroup$ – Ivan Smirnov Jun 5 '17 at 1:34
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My question is not exactly "most common substring with partial repeats," but most common substring with adjacent repeats which continue until the sequence terminates. $\endgroup$ – Web_Designer Jun 3 '17 at 0:30
0
$\begingroup$

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)$.

$\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.