字符串应用之最长公共子序列和最长公共子串

2019-11-14 08:47:14

字体：大中小

来源：转载

供稿：网友

最长公共子序列

Xm $X_m$ 表示X串的前m个字符，即x0,x1...xm−1 ${x_0,x_1...x_{m-1}}$ LCS(Xm,Yn) $LCS(X_m,Y_n)$ 即X的前m个字符和Y的前n个字符的最长公共子序列。

动规方程如下： LCS(Xm,Yn)={LCS(Xm−1,Yn−1)+Xmmax(LCS(Xm−1,Yn),LCS(Xm,Yn−1)),xm=xn,xm≠yn $LCS(X_m,Y_n)=/begin{cases}LCS(X_{m-1},Y_{n-1})+X_m&,{x_m=x_n}//max(LCS(X_{m-1},Y_n),LCS(X_m,Y_{n-1}))&, {x_m/neq y_n}/end{cases}$

//最长公共子序列int longestCommonSubsequence(string A, string B) { int m = A.size(); int n = B.size(); vector<vector<int>>dp(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (A[i] == B[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]); } } } int i = m - 1; int j = n - 1; string s; //记录最长子序列并打印 while (i != -1 && j != -1) { if (A[i] == B[j]) { s += A[i]; --i; --j; } else { if ( (dp[i+1][j ] > dp[i ][j+1])) { --j; } else { --i; } } } string res(s.rbegin(), s.rend()); cout << res << endl; return dp[m][n]; // write your code here}

最长公共子串

最长公共子串，由于匹配的字串必须在A、B串都是连续的，因此在更新dp[i][j]的时候只能从dp[i-1][j-1]。

//最长公共字串int longestCommonSubstring(string &A, string &B) { // write your code here size_t m = A.size(); size_t n = B.size(); int res = 0; vector<vector<int>> dp(m, vector<int>(n)); for (int i = 0; i < static_cast<int>(m); ++i) { for (int j = 0; j < static_cast<int>(n); ++j) { if (A[i] == B[j]) { if (i>0 && j>0) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = 1; } } if (res < dp[i][j]) { res = dp[i][j]; } } } return res;}

上一篇：cuda《学习笔记三》——共享内存和同步

下一篇：python中如何避免中文是乱码

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注