Longest repeated substring

问题描述

    这个问题的描述相对来说比较简单，对于给定的一个string，需要求它里面最长的重复子串。

    那么哪些串算是最长重复子串呢？比如说给定一个string "abc", 它所有可能的子串有"a", "b", "c", "ab", "bc", "abc"这么多种。因为要求是重复子串，则必然有重复的部分。而这个示例里没有重复的部分。针对这种情况可以说它的最长重复子串是一个空串""。

    在举一个示例，比如string "aba"，它的所有可能的子串则有"a", "b", "a", "ab", "ba", "aba"。在这种情况下，我们看到有两个重复的"a"，除此以外则没有其他重复的子串了。因此"a"，就是它的最长重复子串。

    根据前面的讨论，我们发现这个问题存在几个困难点：

    1. 怎么保存它所有的子串。如果所有的都保存的话，对于一个长度为n的串来说，它所有子串则有n * n个。很快就存储爆炸了。

   2. 因为是只要找重复的子串，如何保存和记录重复的子串也是一个需要考虑的地方。

 

分析 

    针对前面的这几个问题我们可以这样来看。对于一个字符串里所有的子串，它们无非都是起始于字符串的索引0, 1, 2...n-1等。所以对于从各索引位置开始到字符串的结尾形成的串中我们需要求的最长子串可以通过互相比较它们之间最长公共部分求出来。

    但是如果就这么盲目的去比较的话，每个元素都要和其他所有元素做一次比较。那么总体需要比较的次数为O(N * N)。相对来说时间复杂度还是有点偏高。

    这个时候，如果把排序这一手法给用上来的话，会带来一个更好的效果。为什么会这么想呢？其实排序，从某种角度来说是把一组字符串按照它们相似的程度从小到大逐渐拉开了。所以在排完序的序列里，相邻的两个元素之间相似度是最接近的。这样的话每次只需要取相邻的两个序列进行比较，然后取得到的最大的那个就可以了。采用这种方式的话，它的时间复杂度相对就简化很多了。排序需要的时间复杂度为O(NlgN)，后续比较的时间复杂度为O(N)。这样总体的效率得到不少的提升。

    概括起来，解决这个问题的思路就是首先取各位置开头到最末尾的子串放到一个数组里。然后再对数组排序。这样最接近的元素就是相邻的两个了。然后再遍历整个序列去比较和取最长的公共子串。这样可以得到如下的代码：

 

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

 

总结 

     求最长重复子串里头最关键的地方就是利用排序的特性，在排序的结果里，相邻的两个元素之间相似度最接近。就好像数字一样，两个相邻的数字更接近一些。这样问题就转化为求相邻元素的最大公共子串。这种思路的转换比较巧妙。

 

参考材料

http://introcs.cs.princeton.edu/java/42sort/LRS.java.html

http://stackoverflow.com/questions/10355103/finding-the-longest-repeated-substring

https://en.wikipedia.org/wiki/Suffix_array