從本文開始要講一個非常重要的問題：文本相似度問題

解決文本相似度問題的算法有很多，本文就先講一個比較簡單的，基於最長公共子串的算法。

如果要比較兩篇文檔的相似度，可以將兩篇文檔看出是兩個字符串序列，將其統一歸一化處理後，可以轉化為最長公共子串的問題。那麼解決最長公共子串的算法又有很多，下面將逐個講解。

一. 暴力解法

直接通過兩個循環枚舉第一個字符串的子串，然後判斷其在第二個字符串中是否包含，並記錄包含第一個字符串子串的最大長度即可。很明顯，這樣的解法時間複雜度是大於O(nm)的，代碼如下

int LS(string x, string y) {
 int maxLen = 0;
 int xlen = x.size();
 int ylen = y.size();
 for (int i = 0; i < xlen; i++) {
 int len = 0;
 string str = "";
 for (int j = i; j < ylen; j++) {
 str += x[j];
 if (y.find(str) == y.npos) {
 break;
 }
 len++;
 }
 maxLen = max(maxLen, len);
 }
 return maxLen; 

}

這裡在判斷是否包含子串時用到了STL的find函數，它的平均時間複雜度為O(m+n)，但最壞時間複雜度為O(mn)，可以將其改為KMP匹配算法，那麼整體時間複雜度為O(m*n*(m+n))。這種暴力算法性能太差，那麼下面基於動態規劃的方法性能又要好很多。

二. 動態規劃法

假如我們用動態規劃的思想，對於兩個字符串，用dp[i][j]來表示同時以x_i和y_j結尾的子串，那麼很明顯當x_i不等於y_j時，dp[i][j]=0，當x_i等於y_j時候，dp[i][j] = dp[i - 1][j - 1] + 1，所以轉移方程如下

那麼代碼也就很容易了，如下

int LS(string x, string y) {
 int maxLen = 0; 

 int xlen = x.size();
 int ylen = y.size();
 for (int i = 0; i <= xlen; i++) {
 for (int j = 0; j <= ylen; j++) {
 if (i == 0 || j == 0) {
 dp[i][j] = 0;
 } else if (x[i - 1] == y[j - 1]) {
 dp[i][j] = dp[i - 1][j - 1] + 1;
 } else {
 dp[i][j] = 0;
 }
 maxLen = max(maxLen, dp[i][j]);
 }
 }
 return maxLen;
}

很明顯，動態規劃法兩個循環，時間複雜度為O(mn)，通常這種時間複雜度也就夠用了。但其實還有其它更優的算法，例如基於後綴數組的最長公共子串求法。

三. 後綴數組法

這個算法稍微複雜一點，通過構造後綴數組，時間複雜度會更低。基於二倍增算法的後綴數組時間複雜度為O(n*log(n))，而基於DC3算法的後綴數組時間複雜度為O(n)。後面有時間我會詳細講解這兩種算法。

可以看出通過計算公共子串的方法來計算兩個串的相似度還存在缺陷，比如很多情況是兩個字符串高度相似，但子串並不一定很長，後面我再講解其它算法來逐步改進這個問題。下一節我會講解更多關於字符串相似度計算算法，歡迎大家關注！

閱讀更多 薛定諤的小貓貓 的文章

關鍵字: 鏡音雙子 文本 搜索引擎