Question

请帮忙///如何计算两个 字符串的最长公共子串

Answer 1

算法：求两个字符串的最长公共子串
原理：
（1） 将连个字符串分别以行列组成一个矩阵。
（2）。若该矩阵的节点对应的字符相同，则该节点值为1。
（3）当前字符相同节点的值 = 左上角(d[i-1, j-1])的值 +1，这样当前节点的值就是最大公用子串的长。
(s2) b c d e
(s1)
a 0 0 0 0
b 1 0 0 0
c 0 2 0 0
d 0 0 3 0

3. 结果：只需以行号和最大值为条件即可截取最大子串

C# code:

[csharp] view plaincopyprint?
public static string MyLCS(string s1, string s2)
{
if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
{
return null;
}
else if (s1 == s2)
{
return s1;
}
int length = 0;
int end = 0;
int[,] a = new int[s1.Length, s2.Length];
for (int i = 0; i < s1.Length; i++)
{
for (int j = 0; j < s2.Length; j++)
{
int n = (i - 1 >= 0 && j - 1 >= 0) ? a[i - 1, j - 1] : 0;
a[i, j] = s1[i] == s2[j] ? 1+n : 0;
if (a[i, j] > length)
{
length = a[i,j];
end = i;
}
}
}
return s1.Substring(end - length + 1, length);
}

Answer 2

CSDN博客上搜一下有这算法