算法：求两个字符串的最大公共子串，谁有最好的实现？100分相送。

Question

算法：求两个字符串的最大公共子串，谁有最好的实现？

Answer 1

LZ看看我这个，得到答案记得要结贴呀，足足写了25分钟 :)
public static String getSubString(String s1, String s2) {
if (s1.length() > s2.length()) {
String temp = s1;
s1 = s2;
s2 = temp;
}
int n = s1.length();
int index = 0;
ok:for (; n > 0; n--) {
for (int i = 0; i < s1.length() - n + 1; i++) {
String s = s1.substring(i, i + n);
if (s2.indexOf(s) != -1) {
index =  i;
break ok;
}
}
}
return s1.substring(index, index + n);
}

Answer 2

to JAVA_WEB(不停地往上爬):我测试了一下，s1，s2:各1000个字符，公共子串4个字符，结果用时1200ms
这个时间能忍受吗？各位高手有何意见？

Answer 3

最长公共子串（LCS）的动态规划算法也是O（n^2)的

Answer 4

http://tonyhuo.spaces.live.com/blog/cns!ff8d04b96c2521ba!152.entry

Answer 5

多谢 JAVA_WEB(不停地往上爬):
结贴了。