在前面我講解了如何通過最長公共子串來求解兩個文本的相似度問題，但它有一定缺陷，舉個例子，看下面的兩個字元串
我愛吃小青菜和各種鮮水果。
我很愛吃青菜與各樣水果。
上面兩個字元串，如果通過計算子串來求相似度，會發現相似度比較低，但如果考慮用最長公共子序列算法求相似度問題，則相似度會很高。子串是有序且連續的，而子序列是有序但不一定連續。
那麼，本文就來講講如何求兩個字元串的最長公共子序列。
一. 暴力解法
跟求最長公共子串一樣，也可以用暴力方法來求解最長公共子序列問題，但是複雜度會更高，時間複雜度是指數級别的，很顯然，這種方法行不通。
二. 動态規劃法
假如兩個字元串分别表示為X=[x_0, x_1, ..., x_m-1]，Y=[y_0, y_1, ..., y_n-1]，通過動态規劃法求最長公共子序列，那麼用dp[i][j]來表示以x_i和y_j為結尾的最長公共子串的長度，那麼
- 當x_i=y_j時，dp[i][j] = dp[i - 1][j - 1] + 1
- 當x_i≠y_j時，dp[i][j]為dp[i - 1][j]和dp[i][j - 1]中最大的那個
是以得到其狀态轉移方程如下
代碼如下
int LCS(string x, string y) { 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] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[xlen][ylen];}
很明顯，基于動态規劃法的最長公共子序列的時間複雜度為O(mn)。
後面會講解更多關于求解文本相似度問題的算法，歡迎大家的關注！