查找字符串中最长的重复子字符串需要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.

解决方法如下

public class Test{
public static void main(String[] args){
System.out.println(findLongestSubstring("i like ike"));
System.out.println(findLongestSubstring("女士，我是亚当"));
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

这是动态规划解决方案的常见 CS 问题。

编辑（对于立杰）：

你在技术上是正确的——这不是完全相同的问题。然而，这并不会使上面的链接变得无关紧要，如果提供的两个字符串相同，则可以使用相同的方法（特别是动态编程）——只需要进行一项修改：不要考虑沿对角线的情况。或者，正如其他人所指出的（例如 LaGrandMere），使用后缀树（也可以在上面的链接中找到）。

编辑（对于迪帕克）：

最长公共子串的 Java 实现（使用动态编程）可以在这里找到。请注意，您需要修改它以忽略“对角线”（查看维基百科图），否则最长的公共字符串将是它本身！