如何找到给定字符串中最长的重复子字符串

我是新的java，我被赋予了查找字符串的最长子字符串的任务。我在网上调查，似乎是解决这个问题的好方法是实施后缀树。请让我知道如何做到这一点，或者如果您有任何其他解决方案。请记住，这是假设要用低水平的Java知识来完成。如何找到给定字符串中最长的重复子字符串

非常感谢。

P.S.测试仪字符串是令人放心的。

/** 
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; 
}

来源

2012-11-03 Dfsdfsdf Dsfsdfdsf

我刚刚研究，希望找到一种替代解决方案。 –

我正在考虑使用两个for循环，并且一个循环会获取字符串的各种子字符串，另一个循环会查看它是否找到字符串其余部分的副本。 –

我不是要求解决方案。因为后缀树看起来更高级别的java编程 –

如果你调试你的代码，你会看到你的代码没有做你的想法。 AFAIK你至少需要三个循环，你不能假设你只会从第一个字符开始。这是一个可能的解决方案。

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; 
}

打印

abcaab

为 “让人放心” 它打印r不s这是我的第一个猜测。 ;）

来源

2012-11-03 19:30:36

非常感谢 –

对于“qwqwabcabc”返回“qw”而不是“abc” – Maksim

什么是OUTER：？这是一个Java概念吗？我明白它在做什么，但不明白它会是什么主题 –

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(); 
    }

来源

2015-02-02 12:41:40

如何找到给定字符串中最长的重复子字符串

回答

相关问题