查找字符串中最長的重複子字符串？

我在下面看到完美的程序。按我來說，它的時間複雜度是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

查找字符串中最長的重複子字符串？

回答

相關問題