Question

Design an efficient algorithm for finding the longest exact repeat within a text.

Answer 1

Solution:

For finding the longest exact repeat within a text we can follow:

We can create the suffix tree using suffix array and LCP array that being said you can achieve the same thing using these(Suffix and LCP) array as if you create suffix tree directly. Thus longest exact repeated problem for a string S of length n can be solved in O(n) time using both the suffix array A and the LCP array L. Will construct suffix array and LCP array.

1. Perform a linear scan through the LCP array in order to find its maximum value max in L[] and the corresponding index i where max is stored.
2. The longest sub-string that occurs at least twice is then given by S[ A[i], A[i]+max − 1 ], where S is the original string.

Time to build Suffix Array is O(n) using DC3 Algorithm.
Time to build LCP array is O(n) using linear scan of Suffix Array.
Time to find the Longest Repeated Sub-String O(n) linear scan of LCP array followed by returning sub-string from original string , its also O(n) in worst case.

Running code in java as follows:

import java.util.Arrays;

public class LRS {

    // 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;
    }



    // read in text, replacing all consecutive whitespace with a single space
    // then compute longest repeated substring
    public static void main(String[] args) {
        String s = StdIn.readAll();
        s = s.replaceAll("\\s+", " ");
        StdOut.println("'" + lrs(s) + "'");
    }
}

Please give thumbsup, if you like it. Thanks.