Comment trouver la plus longue sous-chaîne répétée d'une chaîne donnée

Question

Je suis new java et on m'a assigné pour trouver la plus longue sous-chaîne d'une chaîne. Je recherche en ligne et semble que la bonne façon d'aborder ce problème sera la mise en œuvre de l'arbre des suffixes. S'il vous plaît laissez-moi savoir comment je peux le faire ou si vous avez d'autres solutions. Gardez à l'esprit cela est supposé être fait avec un faible niveau de connaissances Java.

Merci à l'avance.

P.S. la chaîne du testeur est rassurante.

/** 
This method will find the longest substring of a given string. 
String given here is reassuring. 

*/ 
public String longestRepeatedSubstring() 
{ 
    String longestRepeatedSubstring = ""; 
    for (int i = 0; i<text.length(); i++) 
    { 
     String one = text.substring(0,i); 

     for(int o = 0; o<text.length();o++) 
     { 
      Sting two = text.substring(0,o); 
      if(one.equals(two)) 
      { 
       longestRepeatedSubstring = one; 
      } 

     } 

    } 
    return longestRepeatedSubstring; 
} 

Answer 1

Si vous déboguez votre code, vous verrez que le code ne fait pas ce que vous pensez. AFAIK vous avez besoin d'au moins trois boucles et vous ne pouvez pas partir du premier personnage. Voici une solution possible.

public static void main(String[] args) throws IOException { 
    String longest = longestDuplicate("ababcaabcabcaab"); 
    System.out.println(longest); 
} 

public static String longestDuplicate(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; 
} 

impressions

abcaab 

pour elle imprime r pas s "rassurant" qui était ma première supposition. ;)

Answer 2

public static void main(String[] args) { 
     String str = "testingString"; 
     char[] strArr = str.toCharArray(); 
     StringBuilder bm = new StringBuilder(); 
     boolean isPresent = false; 
     int len = strArr.length; 
     int initial =0; 
     int dinitial=0; 

     HashMap<String, String> hm = new HashMap<String,String>(); 
     HashMap<String, String> hl = new HashMap<String,String>(); 
     while(initial<=len-1 && !(dinitial>=len-1)){ 
      if(!hm.isEmpty()){ 
       isPresent = hm.containsValue(strArr[initial]+""); 
       if(!isPresent){ 
        bm.append(strArr[initial]); 
        hm.put(strArr[initial]+"",strArr[initial]+""); 
        if(initial==len-1){ 
         System.out.println("Longest substring is::" + bm); 
         break; 
        } 
       } 
       else if(isPresent){ 
        System.out.println("Longest substring is::" + bm); 
        bm.delete(0, bm.length()); 
        ++dinitial; 
        initial--; 
        hm.clear(); 
       } 
       initial++; 
      } 
      else 
      { 
        bm.append(strArr[initial]); 
        hm.put(strArr[initial]+"",strArr[initial]+""); 
        initial++; 
      } 
     } 
     hm.clear(); 
    }