1 /*
2 经典DP:LCS,最长公共子列
3 zju 1733 hdu 1159 Common Subsequence
4 ymc 2008/09/22
5 题目大意:
6 给定两个字串窜S与T,求S与T的最长公共子列。
7 分析与解题大意:
8 令ans[i][j]为S的前i个字符与T的前j个字符的最长公共字串的
9 长度。则有
10 若S[i-1]==T[j-1],则ans[i][j]=ans[i-1][j-1]+1;
11 否则,ans[i][j]=Max{ans[i-1][j],ans[i][j-1]}。
12 S与T的最长公共子列的长度为ans[n][m],其中n,m分别为
13 S与T的长度。
14 */
15 #include <iostream>
16 #include <string>
17 using namespace std;
18 const int N=1000;
19 char s[N],t[N];
20 int ans[N][N];
21 inline int Max(int x,int y)
22 {
23 return x>y?x:y;
24 }
25 void LCS()
26 {
27 int n=strlen(s);
28 int m=strlen(t);
29 memset(ans,0,sizeof(ans));
30 for(int i=1;i<=n;i++)
31 for(int j=1;j<=m;j++)
32 {
33 if(s[i-1]==t[j-1])
34 {
35 ans[i][j]=ans[i-1][j-1]+1;
36 }
37 else
38 ans[i][j]=Max(ans[i-1][j],ans[i][j-1]);
39 }
40 printf("%d\n",ans[n][m]);
41 }
42 int main()
43 {
44 while(scanf("%s %s",s,t)!=EOF)
45 {
46 LCS();
47 }
48 }
1 //722801 2008-07-26 11:50:30 Accepted 1159 265MS 3908K 788 B G++ whiteTiger DP
2 #include <stdio.h>
3 #include <string.h>
4
5 int lcsCount[1001][1001];
6 char a[1001],b[1001];
7
8 int max(const int x, const int y){
9 return x>y?x:y;
10 }
11
12 void lcs(){
13 memset(lcsCount, 0, sizeof(lcsCount));
14 int x = strlen(a);
15 int y = strlen(b);
16 for(int i = 0; i <= x; i++){
17 for(int j = 0; j <= y; j++){
18 if(i==0 || j ==0)
19 lcsCount[i][j] = 0;
20 else if(a[i-1] == b[j-1])
21 lcsCount[i][j] = lcsCount[i-1][j-1]+1;//状态转移方程
22 else{
23 lcsCount[i][j] = max(lcsCount[i][j-1], lcsCount[i-1][j]);//状态转移方程
24 }
25 }
26 }
27 }
28
29 int main()
30 {
31 while(scanf("%s %s", a, b)!=EOF){
32 lcs();
33 printf("%d\n", lcsCount[strlen(a)][strlen(b)]);
34 }
35
36 return 0;
37 }