查找字符串中最長重複子字符串所需的Java函數？

Question

需要Java函數找到最長的重複子字符串中的

For instance, if the input is 「banana」,output should be "ana" and we have count the number of times it has appeared in this case it is 2.

的解決方法是如下

公共類的測試{
公共靜態無效的主要（字串[] args）{
System.out.println（findLongestSubstring（「我喜歡ike」））;
System.out.println（findLongestSubstring（「madam i'm adam」））; System.out.println（findLongestSubstring（「當生活給你檸檬水，做檸檬」））;
System.out.println（findLongestSubstring（「banana」））;
}

public static String findLongestSubstring(String value) { 
    String[] strings = new String[value.length()]; 
    String longestSub = ""; 

    //strip off a character, add new string to array 
    for(int i = 0; i < value.length(); i++){ 
     strings[i] = new String(value.substring(i)); 
    } 

    //debug/visualization 
    //before sort 
    for(int i = 0; i < strings.length; i++){ 
     System.out.println(strings[i]); 
    } 

    Arrays.sort(strings); 
    System.out.println(); 

    //debug/visualization 
    //after sort 
    for(int i = 0; i < strings.length; i++){ 
     System.out.println(strings[i]); 
    } 

    Vector<String> possibles = new Vector<String>(); 
    String temp = ""; 
    int curLength = 0, longestSoFar = 0; 

    /* 
    * now that the array is sorted compare the letters 
    * of the current index to those above, continue until 
    * you no longer have a match, check length and add 
    * it to the vector of possibilities 
    */ 
    for(int i = 1; i < strings.length; i++){ 
     for(int j = 0; j < strings[i-1].length(); j++){ 
      if (strings[i-1].charAt(j) != strings[i].charAt(j)){ 
       break; 
      } 
      else{ 
       temp += strings[i-1].charAt(j); 
       curLength++; 
      } 
     } 
     //this could alleviate the need for a vector 
     //since only the first and subsequent longest 
     //would be added; vector kept for simplicity 
     if (curLength >= longestSoFar){ 
      longestSoFar = curLength; 
      possibles.add(temp); 
     } 
     temp = ""; 
     curLength = 0; 
    } 

    System.out.println("Longest string length from possibles: " + longestSoFar); 

    //iterate through the vector to find the longest one 
    int max = 0; 
    for(int i = 0; i < possibles.size();i++){ 
     //debug/visualization 
     System.out.println(possibles.elementAt(i)); 
     if (possibles.elementAt(i).length() > max){ 
      max = possibles.elementAt(i).length(); 
      longestSub = possibles.elementAt(i); 
     } 
    } 
    System.out.println(); 
    //concerned with whitespace up until this point 
    // "lemon" not " lemon" for example 
    return longestSub.trim(); 
} 

}

Answer 1

This is a common CS problem with a dynamic programming solution.

Edit（對於麗潔）：

您是技術上是正確的 - 這是不準確的同樣的問題。然而，如果兩個字符串都是相同的 - 只需要做一個修改：不要考慮沿對角線的情況，但是這不會使上面的鏈接無關並且可以使用相同的方法（特別是w.r.t.動態編程）。或者，正如其他人指出的那樣（例如LaGrandMere），使用後綴樹（也可以在上面的鏈接中找到）。

（對於迪帕克）編輯：

A Java implementation of the Longest Common Substring (using dynamic programming) can be found here。請注意，您需要修改它以忽略「對角線」（查看維基百科圖），或者最長的常用字符串本身就是！

Answer 2

在Java中：Suffix Tree。

感謝那些已經發現如何解決它，我不知道。