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

我是新的java，我被赋予了分配以找到字符串中最长的子字符串。 我在网上研究，似乎解决这个问题的好方法是实现后缀树。 如果您有任何其他解决方案，请告诉我如何做到这一点。 请记住，这是假设用低水平的java知识完成的。

谢谢你。

PS测试仪字符串令人放心。

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

如果您调试代码，您将看到代码没有按照您的想法进行。 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 

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

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 hm = new HashMap(); HashMap hl = new HashMap(); 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(); }