最长公共子系列,简单的dp,不过注意有空格,所以,在读字符串的时候,尽量用gets读,这样基本没问题
#include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; int dp[1001][1001]; int MAX(int x,int y) { if (x>y) return x; else return y; } int main() { char str1[1001],str2[1001]; int sum; while(gets(str1)!=NULL) { gets(str2); memset(dp,0,sizeof(dp)); int len1,len2; len1=strlen(str1); len2=strlen(str2); for (int i=1;i<=len1;i++) for (int j=1;j<=len2;j++) { if (str1[i-1]==str2[j-1]) sum=1; else sum=0; dp[i][j]=MAX(dp[i-1][j],MAX(dp[i][j-1],dp[i-1][j-1]+sum)); } cout<<dp[len1][len2]<<endl; } return 0; }
UVA 10405 Longest Common Subsequence,布布扣,bubuko.com
UVA 10405 Longest Common Subsequence
原文:http://www.cnblogs.com/chensunrise/p/3705504.html