我需要找到 n 个字符串中最长的公共子字符串并在我的项目中使用结果。
java中是否有任何现有的实现/库已经这样做了?
并发树呢?
它是Maven Central 中提供的一个小型 (~100 KB) 库。该算法使用基数和后缀树的组合。众所周知,它具有线性时间复杂度(维基百科)。
public static String getLongestCommonSubstring(Collection<String> strings) {
LCSubstringSolver solver = new LCSubstringSolver(new DefaultCharSequenceNodeFactory());
for (String s: strings) {
solver.add(s);
}
return solver.getLongestCommonSubstring().toString();
}
我们可以使用下面的代码来识别 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;
}
这个页面几乎以多种语言准确地给出了你想要的东西。
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;
}
好吧,您可以尝试通过将 n 个字符串放入一个遍历所有字符串的循环中来扩展 wikipedia ( http://en.wikipedia.org/wiki/Longest_common_substring_problem ) 的版本。
public String findLongestCommonSubstring(String source, String dest) {
int table[][] = new int[source.length() + 1][dest.length() + 1];
for (int col = 0; col < table[0].length; col++) {
table[0][col] = 0;
}
for (int row = 0; row < table.length; row++) {
table[row][0] = 0;
}
int max = 0;
int index = 0;
for (int row = 1; row < table.length; row++) {
char sourceChar = source.charAt(row - 1);
for (int col = 1; col < table[row].length; col++) {
char destChar = dest.charAt(col - 1);
if (sourceChar == destChar) {
table[row][col] = table[row - 1][col - 1] + 1;
if (table[row][col] > max) {
max = table[row][col];
index = row;
}
} else {
table[row][col] = 0;
}
}
}
return source.substring(index - max, index);
}