POJ 1458 Common Subsequence——LCS

POJ 1458 Common Subsequence——LCS

#include #include #include #include using namespace std;const int maxn = 5000;char str1[maxn], str2[maxn];int n, m, dp[maxn][maxn];int main() { while (~scanf("%s %s", str1 + 1, str2 + 1)) { n = strlen(str1 + 1), m = strlen(str2 + 1); dp[0][0] = dp[0][1] = dp[1][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (str1[i] == str2[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } printf("%d\n", dp[n][m]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。