North Rivers: Longest Repeated Substring

You are to find the longest repeated substring in a given text. Repeated substrings may not overlap. If more than one substring is repeated with the same length, print the first one you find.(starting from the beginning of the text). NOTE: The substrings can't be all spaces.
Suffix Array

banana return an
Brute force - O(n^3)
we compare the substring starting at each string position i with the substring starting at each other starting position j, keeping track of the longest match found.

Suffix Array
The key to the algorithm’s correctness is that every substring appears somewhere as a prefix of one of the suffixes in the array. After sorting, the longest repeated substrings will appear in adjacent positions in the array. Thus, we can make a single pass through the sorted array, keeping track of the longest matching prefixes between adjacent strings.

Time complexity: O(n^2logn) - we can use nlogn to build suffix array, Space complexity: O(n)

http://yuanhsh.iteye.com/blog/2186611
http://introcs.cs.princeton.edu/java/42sort/LRS.java.html
http://yuanhsh.iteye.com/blog/2186611

    // return the longest common prefix of s and t
    public static String lcp(String s, String t) {
        int n = Math.min(s.length(), t.length());
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != t.charAt(i))
                return s.substring(0, i);
        }
        return s.substring(0, n);
    }


    // return the longest repeated string in s
    public static String lrs(String s) {

        // form the N suffixes
        int N  = s.length();
        String[] suffixes = new String[N];
        for (int i = 0; i < N; i++) {
            suffixes[i] = s.substring(i, N); 
        }

        // sort them
        Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes
        String lrs = "";
        for (int i = 0; i < N - 1; i++) {
            String x = lcp(suffixes[i], suffixes[i+1]);
            if (x.length() > lrs.length())
                lrs = x;
        }
        return lrs;
    }

X. Using Suffix Tree

Time complexity: O(n), Space complexity: O(n)
http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/

Then for each two adjacent suffixes on the sorted suffix array, count the length of the common prefix (Note: should avoid counting the overlapped part). The longest repeated prefix appearing first on the original input string is the result. 
Code from http://algs4.cs.princeton.edu/63suffix/LongestCommonSubstring.java.html

    public static String lrs(String s) {

        // form the N suffixes
        int N  = s.length();
        String[] suffixes = new String[N];
        for (int i = 0; i < N; i++) {
            suffixes[i] = s.substring(i, N);
        }

        // sort them
        Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes
        String lrs = "";
        for (int i = 0; i < N - 1; i++) {
            String x = lcp(suffixes[i], suffixes[i+1]);
            if (x.length() > lrs.length())
                lrs = x;
        }
        return lrs;
    }

Dynamic Programming
Check Dynamic Programming | Set 29 (Longest Common Substring)

/* Returns length of longest common substring of X[0..m-1] and Y[0..n-1] */

int LCSubStr(char *X, char *Y, int m, int n)

{

    // Create a table to store lengths of longest common suffixes of

    // substrings.   Notethat LCSuff[i][j] contains length of longest

    // common suffix of X[0..i-1] and Y[0..j-1]. The first row and

    // first column entries have no logical meaning, they are used only

    // for simplicity of program

    int LCSuff[m+1][n+1];

    int result = 0;  // To store length of the longest common substring

    /* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */

    for (int i=0; i<=m; i++)

    {

        for (int j=0; j<=n; j++)

        {

            if (i == 0 || j == 0)

                LCSuff[i][j] = 0;

            else if (X[i-1] == Y[j-1])

            {

                LCSuff[i][j] = LCSuff[i-1][j-1] + 1;

                result = max(result, LCSuff[i][j]);

            }

            else LCSuff[i][j] = 0;

        }

    }

    return result;

}




Suppose we first don't consider the constraint of no overlap. The idea is to find the longest repeated suffix for all pairs of prefixes of the string str. The length of the longest repeated suffix for prefixes str[1..i] andstr[1..j] is:

c(i, j) = 1) c(i-1, j-1) + 1   if str[i] == str[j];
          2) 0                 otherwise.

The maximum of c(i, j) (1 <= i, j <= n) is the length of longest repeated substring (suffix) of str.

Now consider the non-overlapping constraint, otherwise the above process will give us the string itself. Look at prefixes str[1..i] and str[1..j], the end indices of their suffixes are i and j (for simplicity, suppose i <= j), respectively. If their common suffix is longer than j-i, the two suffixes must overlap. The overlapped part should not be counted and the above recursion should be modified as:

c(i, j) = 1) c(i-1, j-1) + 1   if str[i] == str[j] && abs(i-j) > c(i-1, j-1);
          2) 0                 otherwise.

std::string repeated_substring(std::string &str) {
    int len = str.length();

    int **c = new int*[len + 1];
    for (int i = 0; i <= len; ++i)
        c[i] = new int[len + 1];
    for (int i = 0; i <= len; ++i) {
        c[i][0] = 0;
        c[0][i] = 0;
    }

    int max_len = 0, index = len + 1;
    for (int i = 1; i <= len; ++i) {
        for (int j = 1; j <= len; ++j) {
            if (str[i-1] == str[j-1] && abs(i-j) > c[i-1][j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
                if (c[i][j] > max_len) {
                    max_len = c[i][j];
                    index = std::min(i, j);
                }
            } else {
                c[i][j] = 0;
            }
        }
    }
    
    for (int i = 0; i <= len; ++i)
        delete[] c[i];
    delete[] c;
 
    if (max_len > 0) {
        std::string ret = str.substr(index - max_len, max_len);
        for (int i = 0; i < max_len; ++i)
            if(ret[i] != ' ')
                return ret;
    }

    return "NONE";
}

Read full article from North Rivers: Longest Repeated Substring