Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 65333 | Accepted: 27331 |
Description
Input
Output
Sample Input
abcfbc abfcab programming contest abcd mnp
Sample Output
4 2 0
最长公共子序列问题(LCS) 其状态转换式为:A[i] = A[j]时,d(i,j) = d(i-1,j-1) + 1,否则d(i,j) = max{d(i-1,j),d(i,j-1)}
这个用char数组吧,用string可能出错,。。。打表
C++代码:
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> using namespace std; const int maxn = 10000; int dp[maxn][maxn]; char s1[maxn]; char s2[maxn]; int len1,len2; int main(){ while(~scanf("%s%s",s1,s2)){ len1 = strlen(s1); len2 = strlen(s2); for(int i = 0; i <= len1; i++){ dp[i][0] = 0; } for(int j = 0; j <= len2; j++){ dp[0][j] = 0; } for(int i = 1; i <= len1; i++){ for(int j = 1; j <= len2; j++){ if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i][j-1],dp[i-1][j]); } } printf("%d\n",dp[len1][len2]); } return 0; }
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。