Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 67653 Accepted: 28245
Description
Input
Output
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4 2 0
解题思路：
重点在于状态转移方程的书写，这一题讲义PPT中画的图很好，言简意赅，我一开始想的是计算s2中以xk为终点的字串在s1中的公共子序列，但是发现自己对题意的理解有误，子串中的各字母是可以隔开的，因此逐个字符比较是最好的。既然是逐个字符相比较，那么自然也要考虑s1的位置。
AC代码：
#include<iostream> #include<algorithm> #include<cstring> using namespace std; char s1[1000]; char s2[1000]; int maxLen[1000][1000]; int main() { while (cin >> s1 >> s2) { int length1 = strlen(s1); int length2 = strlen(s2); for (int i = 0; i <= length1; i++) maxLen[i][0] = 0; for (int j = 0; j <= length1; j++) maxLen[0][j] = 0; for (int i = 1; i <= length1; i++) { for (int j = 1; j <= length2; j++) { if (s1[i - 1] == s2[j - 1]) maxLen[i][j] = maxLen[i - 1][j - 1] + 1; else maxLen[i][j] = max(maxLen[i - 1][j], maxLen[i][j - 1]); } } cout << maxLen[length1][length2] << endl; } return 0; }
POJ 1458 Common Subsequence（最长公共子序列）
原文：https://www.cnblogs.com/yun-an/p/10960726.html