用于n个字符串的最长公共子字符串的Java实现

我需要找到n个字符串中最长的公共子字符串，并在我的项目中使用结果。

java中是否有现有的实现/库已经这样做了？

感谢您提前回复。

Answer 1

我们可以使用下面的代码来识别n个字符串中最长的公共子字符串

public static String identifyCommonSubStrOfNStr(String [] strArr){ String commonStr=""; String smallStr =""; //identify smallest String for (String s :strArr) { if(smallStr.length()< s.length()){ smallStr=s; } } String tempCom=""; char [] smallStrChars=smallStr.toCharArray(); for (char c: smallStrChars){ tempCom+= c; for (String s :strArr){ if(!s.contains(tempCom)){ tempCom=c; for (String s :strAarr){ if(!s.contains(tempCom)){ tempCom=""; break; } } break; } } if(tempCom!="" && tempCom.length()>commonStr.length()){ commonStr=tempCom; } } return commonStr; } 

Answer 2

并发树怎么样？

它是Maven Central中的一个小型（~100 KB）库。 该算法使用Radix和Suffix Trees的组合。 众所周知，它具有线性时间复杂度 （ 维基百科 ）。

 public static String getLongestCommonSubstring(Collection strings) { LCSubstringSolver solver = new LCSubstringSolver(new DefaultCharSequenceNodeFactory()); for (String s: strings) { solver.add(s); } return solver.getLongestCommonSubstring().toString(); } 

Answer 3

这个页面几乎可以用很多语言提供你想要的内容。

 public static int longestSubstr(String first, String second) { if (first == null || second == null || first.length() == 0 || second.length() == 0) { return 0; } int maxLen = 0; int fl = first.length(); int sl = second.length(); int[][] table = new int[fl][sl]; for (int i = 0; i < fl; i++) { for (int j = 0; j < sl; j++) { if (first.charAt(i) == second.charAt(j)) { if (i == 0 || j == 0) { table[i][j] = 1; } else { table[i][j] = table[i - 1][j - 1] + 1; } if (table[i][j] > maxLen) { maxLen = table[i][j]; } } } } return maxLen; } 

Answer 4

那么你可以尝试通过将它放入一个遍历所有字符串的循环来扩展wikipedia（ http://en.wikipedia.org/wiki/Longest_common_substring_problem ）的版本。