Java-Funktion zum Suchen der längsten duplizierten Teilzeichenfolge in einer Zeichenfolge benötigt?

Question

Java-Funktion benötigt den längsten doppelten String in einem String

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.

Die Lösung ist als unten

public class Test {
public static void main (String [] args) zu finden {
System.out.println (findLongestSubstring ("Ich mag Ike"));
System.out.println (findLongestSubstring ("Frau ich bin Adam"));
System.out.println (findLongestSubstring ("Wenn das Leben dir Limonade gibt, mach Zitronen"));
System.out.println (findLongestSubstring ("Banane"));
}

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 (für lijie):

Sie sind technisch korrekt - das ist nicht die genaue gleiche Problem. Dies macht jedoch die obige Verknüpfung nicht irrelevant, und der gleiche Ansatz (insbesondere dynamische Programmierung) kann verwendet werden, wenn beide bereitgestellten Zeichen gleich sind - es muss nur eine Änderung vorgenommen werden: Betrachten Sie den Fall nicht entlang der Diagonalen. Oder, wie andere darauf hingewiesen haben (z. B. LaGrandMere), verwenden Sie einen Suffixbaum (ebenfalls im obigen Link zu finden).

Edit (Deepak):

A Java implementation of the Longest Common Substring (using dynamic programming) can be found here. Beachten Sie, dass Sie es ändern müssen, um "die Diagonale" zu ignorieren (sehen Sie sich das Wikipedia-Diagramm an), oder die längste gemeinsame Zeichenkette wird selbst sein!

Answer 2

In Java: Suffix Tree.

Dank denen, die es gelöst haben, wusste ich nicht.