查找字符串中最长的重复子字符串？

我在下面看到完美的程序。按我来说，它的时间复杂度是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 < n-1; i++) { 
      String x = lcp(suffixes[i], suffixes[i+1]); 
      if (x.length() > lrs.length()) 
       lrs = x; 
     } 
     return lrs; 
    } 



    public static void main(String[] args) { 
     String s = "MOMOGTGT"; 
     s = s.replaceAll("\\s+", " "); 
     System.out.println("'" + lrs(s) + "'"); 

    } 

}

来源

2016-10-16 user3198603

如果代码是已经在运行，那么这可能属于[代码评论]（http://codereview.stackexchange.com）。 –

通过不创建尽可能多的子字符串，可以使其更快（尽管不是渐近地）。例如，'lcp'只能返回前缀长度，并且保留'i'和那个返回值来存储“迄今为止的最大值”。 –

-1

看一看这个算法geeksforgeeks给出的，这可能会有帮助：

http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/

来源

2016-10-16 13:22:05

-2

我发现这个解决方案

public class longestDuplicate { 

public static void main(String[] args) { 
    String longest = "ababcaabcabcaab"; 
    String result = longestDup(longest); 
    System.out.println(result); 
} 

public static String longestDup(String text) { 
    String longest = ""; 
    for (int i = 0; i < text.length() - 2 * longest.length() * 2; i++) { 
     OUTER: 
     for (int j = longest.length() + 1; j * 2 < text.length() - i; j++) { 
      String find = text.substring(i, i + j); 
      for (int k = i + j; k <= text.length() - j; k++) { 
       if (text.substring(k, k + j).equals(find)) { 
        longest = find; 
        continue OUTER; 
       } 
      } 
      break; 
     } 
    } 

    return longest; 
}}

结果：abcaab

来源

2017-12-15 03:33:40

查找字符串中最长的重复子字符串？

回答

相关问题