736
技術社區[雲棲]
LCS (Longest Common Subsequence) 字符串最長公共子串算法
LCS (Longest Common Subsequence) 算法用於找出兩個字符串最長公共子串。
算法原理：
(1) 將兩個字符串分別以行和列組成矩陣。
(2) 計算每個節點行列字符是否相同，如相同則為 1。
(3) 通過找出值為 1 的最長對角線即可得到最長公共子串。
人 民 共 和 時 代
中 0, 0, 0, 0, 0, 0
華 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 1, 0, 0, 0, 0
共 0, 0, 1, 0, 0, 0
和 0, 0, 0, 1, 0, 0
國 0, 0, 0, 0, 0, 0
為進一步提升該算法，我們可以將字符相同節點(1)的值加上左上角(d[i-1, j-1])的值，這樣即可獲得最大公用子串的長度。如此一來隻需以行號和最大值為條件即可截取最大子串。
人 民 共 和 時 代
中 0, 0, 0, 0, 0, 0
華 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 2, 0, 0, 0, 0
共 0, 0, 3, 0, 0, 0
和 0, 0, 0, 4, 0, 0
國 0, 0, 0, 0, 0, 0
算法實現：
public static string LCS(string s1, string s2)
{
if (s1 == s2)
return s1;
else if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
return null;
var d = new int[s1.Length, s2.Length];
var index = 0;
var length = 0;
for (int i = 0; i < s1.Length; i++)
{
for (int j = 0; j < s2.Length; j++)
{
// 左上角值
var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;
// 當前節點值 = "1 + 左上角值" : "0"
d[i, j] = s1[i] == s2[j] ? 1 + n : 0;
// 如果是最大值，則記錄該值和行號
if (d[i, j] > length)
{
length = d[i, j];
index = i;
}
}
}
return s1.Substring(index - length + 1, length);
}
最後更新：2017-04-02 06:51:39