Longest Non-Overlapping Repeated Substring using Suffix Tree/Array (Algorithm Only)

Generate suffix array and sort in O(nlogn).ps: There is more effective algorithm like DC3 and Ukkonen algorithm. example:

String : ababc Suffix array: start-index of substring | substring
0 - ababc
2 - abc
1 - babc
3 - bc
4 - c

compare each two consecutive substring and get common prefix with following constraint:
Say i1 is index of substring "ababc": 0
say i2 is index of substring "abc":2
common prefix is "ab" , length of common prefix is len

abs(i1-i2) >len //avoid overlap

go through suffix array with solution, and you will get the result of "ababc", which is "ab";

The whole solution will run O(nlogn)

However, there will be a special case: "aaaaa" that this solution can't solve thoroughly.
Welcome to discuss and come up to a solution of O(nlogn) but not O(n^2)

Since I had a hard time finding a clear description of a working algorithm to obtain the longest non-overlapping repeated substrings using a suffix tree, I'd like to share the version I gathered from various sources.

Algorithm

1. Construct the suffix tree for the input string S (terminated with a special character that doesn't occur in S). Each leaf node corresponds to a suffix S_i of S and is assigned the corresponding start position i of S_i in S.
2. Assign each node in the tree a pair (i_min, i_max) that indicates the minimum and maximum suffix indices at that subtree.
   1. For each leaf i_min = i_max = i.
   2. For each inner node i_min is the minimum, i_max is the maximum index of all descendant nodes' indices.
3. For all inner nodes v, let P_v denote the string obtained by concatenating all edge labels (prefixes) on the path from the root to v. Collect all such P_v that satisfy i_min + length(P_v) ≤ i_max for the corresponding i_min and i_max at v.
4. The longest of those P_v is the longest non-overlapping substring of S that occurs at least twice.

Explanation

If a substring of S occurs at least twice in S, it is the common prefix P of two suffixes S_i and S_j, where i and j denote their respective start position in S. Hence, there exists an inner node v in the suffix tree for S that has two descendant leaves that correspond to i and j such that the concatenation of all edge labels of the path from the root to v is equal to P.

The deepest such node v (in terms of the length of its corresponding prefix) marks the longest, possibly overlapping repeated substring in S. To make sure no overlapping substrings are considered, we have to make sure that P is no longer than the distance between i and j.

We therefore calculate the minimum and the maximum indices i_min and i_max for each node, which correspond to the positions of the leftmost and the rightmost suffixes of S that share a common prefix. The minimum and maximum indices at a node can be easily obtained from the values of their descendants. (The indices calculation would be more complicated if we were looking for the longest substrings that occur at least k times, because then the distances of all descendants' indices had to be considered, not just two that are the farthest apart.) By considering only prefixes P that satisfy i_min + length(P) ≤ i_max we make sure the P starting at S_i is short enough to not overlap with the suffix S_j.

Additional notes

• A suffix tree for strings of length n can be constructed in Θ(n) time and space. The modifications for this algortihm don't worsen the asymptotic bahavior such that the overall running time still is in Θ(n).
• This algorithm doesn't find all possible solutions. If there are several non-overlapping longest substrings, only the substring starting at the largest position is found.
• It should be possible to modify the algorithm to also count the number of repetitions of the longest non-overlapping substring or to find only solutions with at least k repetitions. For this not only the minimum and maximum inidices have to be considered, but the indices of all subtrees at a node. The above range condition then has to hold for each adjacent indices pair.

Unfortunately, the solution proposed by Perkins will not work. We can't brute force our way through solutions to find a long repeated non-overlapping substring. Consider the suffix tree for banana: http://en.wikipedia.org/wiki/Suffix_tree. The "NA" branching node with "A" as its parent will be considered first, since it has the biggest length and is a branching node. But its constructed string "ANA" is overlapping, so it will be rejected. Now, the next node to consider with be "NA" which will show a non-overlapping length of 2, but substring "AN" will never be considered since it was already represented in the ANA string already considered. So if you're searching for all repeated non-overlapping substrings, or when there's a tie you want the first alphabetical one, you're out of luck.

Apparently there is an approach involving suffix trees that works, but the simpler approach is laid out here: http://rubyquiz.com/quiz153.html

Hope this helps!

By constructing a suffix tree, all suffixes sharing a prefix P will be descendants of a common ancestor in the tree. By storing the maximum and minimum index of the the suffixes of that sub tree, we can guarantee a repeated non-overlapping substring of length min(depth, max-min) where max-min is the distance between them and depth is the length of their common prefix. The desired value is the node with maximum such value.

First, compute the suffix array of the string. Then compute the longest common prefix array (this can also be done in linear time). That is, for all i, LCP[i] is the length of the longest common prefix of the ith smallest suffix and the (i+1)th smallest suffix.

Let S be the longest substring that is repeated without overlapping, and let l be the length of S. S may occur a few times in the string; let's say lo is the first index at which it appears, and hi is the last index. It must be the case that hi - lo is at least the length of S (otherwise the occurrences would overlap).

The suffix starting at position lo and the suffix starting at position hi have a common prefix whose length is at least that of S. That means that if i is the lexicographical rank of the suffix starting at position lo, and j is the lexicographical rank of the suffix starting at position hi, and i is less than j, then the values LCP[i], LCP[i+1], ..., LCP[j-1] are all greater than or equal to l. If j is less than i, then LCP[j], LCP[j+1], ..., LCP[i-1] are all greater than or equal to l.

In other words a repeated substring of length l is always associated with a subarray (that is, a set of consecutive elements) in the LCP array that are all greater than or equal to l.

So what we will do is consider all "maximal rectangles" inside the LCP array. Suppose we have a subarray of the LCP array, where the minimum value in that subarray is m. This subarray represents a set of suffixes of the original string that all start with the same m characters. In order to find a pair of such suffixes that are as far apart from each other as possible (i.e., have as long a common prefix as possible without overlapping) we will surely want this subarray to be as large as possible. So we extend it to the left and to the right as much as possible. A "maximal rectangle" is a subarray that can't be extended any further. So for example, in the array {2, 3, 2, 1, 4}, the subarray {2, 3, 2} is maximal because it can't be extended to the left, and if it were extended to the right then it would contain 1, which is smaller than the current minimum element.

To find all maximal rectangles in the LCP array is equivalent to finding the all nearest smaller values (ANSV) on both sides. This is because every maximal rectangle has some smallest element (possibly not unique) and that smallest element is the one that restricts whether the rectangle can be extended to the left or to the right: namely, you can't extend it in one direction any further once you encounter an element that's smaller than the smallest element.

Now recall that if you have a rectangle LCP[i], LCP[i+1], ..., LCP[j-1] whose minimum value is m, then it represents a set of suffixes that start at indices SA[i], SA[i+1], ..., SA[j] (where SA is the suffix array) and have a common prefix of length m. Let d be the difference between the minimum of these SA values and the maximum. If d is greater than or equal to m, then it means there are two substrings of length m that are equal and whose starting points are at least d apart, and since d is greater than m, they're disjoint. If d is less than m, then we can only find two equal disjoint substrings of length d, not m: if we were to extend them any further to the right, then they would overlap. So the best disjoint repeating substring length we can get from a given maximal rectangle is the minimum of its d and m values. By taking the maximum over all maximal rectangles we get the answer to the original problem.

If you compute all the maximal rectangles as the first step, you will find yourself then having to compute a bunch of range minimum queries to get the minimum and maximum SA values for each rectangle. This will typically make your solution O(n log n). However, with a modification to the stack-based ANSV algorithm we can also compute the minimum and maximum SA values as part of the linear-time ANSV computation, giving an overall linear time algorithm.

To wit, consider a pair of arrays A and B, each with n elements. We want to produce the following output:

• N, the "nearest smaller index on the left" array, that is, for each i, N[i] is the largest j such that A[j] is strictly less than A[i]
• M, where M[i] is the minimum of B[N[i]], B[N[i]+1], ..., B[i]

The regular ANSV problem only asks to compute N, which we do by keeping a stack of indices, and when we process A[i], we pop off all indices j_1, ..., j_m from the stack such that A[j_1], ..., A[j_m] are greater than or equal to A[i], before pushing i on to the stack. In the modified version, we can compute M as well using the formula M[i] = min(B[i], M[j_1], ..., M[j_m]).

In the original problem we have to scan in both directions, and in each scan we have to compute both the range minimum and the range maximum.

The simplest solution is something of a brute force attack. You have an algorithm to find the longest overlapping-allowed string, use it, check if that answer has overlaps, if so, find the second longest, check and see if it has overlaps, and so on. That reduces it to your existing search algorithm, then a regex count operation.

This could be solved using results given in "Computing Longest Previous non-overlapping Factors" (see http://dx.doi.org/10.1016/j.ipl.2010.12.005 )

Complete code:

#include <bits/stdc++.h>
using namespace std;
int cplen(string a,string b){
    int i,to=min(a.length(),b.length());
    int ret=0;
    for(i=0;i<to;i++){
        if(a[i]==b[i])ret++;
        else {
            return ret;}
        }
    return ret;
    }
int main(){
    {
        int len,i;
        string str;
        cin>>str;
        len=str.length();
        vector<pair<string,int> >vv;
        map<char,int>hatbc;
        string pp="";
        for(i=len-1;i>=0;i--){
            hatbc[str[i]]++;
            pp=str.substr(i,len-i);
            vv.push_back(make_pair(pp,i));
            }
        if(len==1 || (int)hatbc.size()==len){
            printf("0\n");
            continue;
            }
        if(hatbc.size()==1){
            printf("%d\n",len/2);
            continue;
            }
        char prev=str[0];
        int foo=1,koo=0;
        for(i=1;i<len;){
            while(str[i]==prev && i<len){i++;foo++;}
            prev=str[i];
            i+=1;
            if(koo<foo)koo=foo;
            foo=1;
            }

        sort(vv.begin(),vv.end());
        int ans=0;
        ans=koo/2;
        for(i=1;i<(int)vv.size();i++){
            int j=i-1;
            int a=vv[j].second,b=vv[i].second;
            string sa=vv[j].first,sb=vv[i].first;
            int cpl;
            cpl=cplen(sa,sb);
            if(abs(a-b)>=cpl)
                ans=max(ans,cpl);
            }
        printf("%d\n",ans);
        }
    return 0;
    }

Complexity : O(n*log(n)) (due to sorting)

We use the longest common prefix (LCP) array and suffix array to solve this problem in O(n log n) time.

The LCP array gives us the longest common prefix between two consecutive suffixes in the suffix array.

After constructing the LCP array and the suffix array, we can binary search for the length of the answer.

Suppose the string is "acaca$". The suffix array is given in the code snippet as a table.

<table border="1">
<tr><th>Suffix Array index</th><th>LCP</th><th>Suffix (implicit)</th></tr>
<tr><td>5</td><td>-1</td><td>$</td></tr>
<tr><td>4</td><td>0</td><td>a$</td></tr>
<tr><td>2</td><td>1</td><td>aca$</td></tr>
<tr><td>0</td><td>3</td><td>acaca$</td></tr>
<tr><td>3</td><td>0</td><td>ca$</td></tr>
<tr><td>1</td><td>2</td><td>caca$</td></tr>
</table>

Let's binary search for the length of the answer.

If we have a certain answer, let the two substrings correspond to two suffixes.

There is no guarantee that these suffixes are consecutive in the suffix array. However, if we know the length of the substring, we can see that every entry in the LCP table between the two suffixes of the substrings is at least that number. Also, the difference between the indices of the two suffices must be at least that number.

Guessing that the length of the substring is a certain amount, we can consider consecutive runs of LCP array entries which are at least that amount. In each consecutive run, find the suffix with the largest and smallest index.

How do we know our guess is a lower bound?

If the distance between the largest and smallest index in some [consecutive runs of LCP array entries which are at least our guess] is at least our guess, then, our guess is an attainable lower bound.

How do we know our guess is too big?

If the distance between the largest and smallest index in all [consecutive runs of LCP array entries which are at least our guess] is smaller than our guess, then, our guess is too big.

How do we find the answer given the length of the answer?

For each [consecutive runs of LCP array entries which are at least the answer], find the lowest and highest indices. If they differ by at least the answer, then we return that the longest non-overlapping repeated substrings begin at these indices.

In your example, "acaca$", we can find that the length of the answer is 2.

All the runs are: "aca$", "acaca$", and the distance between the lower and higher indices is 2, resulting in the repeated substring "ac".

"caca$", "ca$", and the distance between the lower and higher indices is 2, resulting in the repeated substring "ca".