在前面我講解了如何通過最長公共子串來求解兩個文本的相似度問題，但它有一定缺陷，舉個例子，看下面的兩個字符串

我愛吃小青菜和各種鮮水果。

我很愛吃青菜與各樣水果。

上面兩個字符串，如果通過計算子串來求相似度，會發現相似度比較低，但如果考慮用最長公共子序列算法求相似度問題，則相似度會很高。子串是有序且連續的，而子序列是有序但不一定連續。

那么，本文就來講講如何求兩個字符串的最長公共子序列。

一. 暴力解法

跟求最長公共子串一樣，也可以用暴力方法來求解最長公共子序列問題，但是復雜度會更高，時間復雜度是指數級別的，很顯然，這種方法行不通。

二. 動態規劃法

假如兩個字符串分別表示為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)。

后面會講解更多關于求解文本相似度問題的算法，歡迎大家的關注！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的两个字符串的最长公共子序列长度_程序员编程算法，解决文本相似度问题的最长公共子序列算法！...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。