字符串應用之最長公共子序列和最長公共子串

2019-11-11 07:39:27

字體：大中小

來源：轉載

供稿：網友

最長公共子序列

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;}

上一篇：網絡流知識大全

下一篇：lintcode | 克隆二叉樹