在字符串中找到最长的重复子字符串？
我遇到了下面看起来很完美的程序。 根据我的时间复杂度是nlogn，其中n是String的长度。
n用于存储不同的字符串，nlog用于排序，n用于比较。 所以时间复杂度是nlogn。 空间复杂度为n，用于存储n个子串
我的问题是它可以进一步优化吗？
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 lrs.length()) lrs = x; } return lrs; } public static void main(String[] args) { String s = "MOMOGTGT"; s = s.replaceAll("\\s+", " "); System.out.println("'" + lrs(s) + "'"); } } 看看geeksforgeeks中给出的这个算法，这可能会有所帮助：
http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/