Нужна ли функция 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.

Решение выглядит следующим образом:

открытый класс Test {
открытый статическийvoid main (String [] args) {
System.out.println (findLongestSubstring ("i like 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

Это общая проблема CS с решением динамического программирования.

Редактировать (для lijie):

Вы технически правы - это не точная та же проблема. Однако это не делает указанную выше ссылку неактуальной, и тот же подход (в частности, к динамическому программированию) можно использовать, если обе предоставленные строки одинаковы - необходимо внести только одну модификацию: не рассматривать случай по диагонали. Или, как указали другие (например, LaGrandMere), используйте дерево суффиксов (также найденное в приведенной выше ссылке).

Редактировать (для Дипака):

Java-реализацию самой длинной общей подстроки (с использованием динамического программирования) можно найти здесь Обратите внимание, что вам нужно будет изменить его так, чтобы он игнорировал «диагональ» (посмотрите на диаграмму Википедии), иначе самая длинная общая строка будет сама!

Answer 2

В Java: Дерево суффиксов .

Спасибо тем, кто нашел, как ее решить, я не знал.