poj(1458)(最长公共子序列)

时间：2011-03-15 来源：FC WORLD!!!

View Code 1 //#include"iostream"
2 #define M 30010
3 using namespace std;
4 int c[2][M];
5 int Max(int a ,int b)
6 {
7 return a>b?a:b;
8 }
9 void LCD(char aa[], char bb[], int x, int y)
10 {
11 int i,j;
12 for(i=0;i<=y;i++)
13 c[0][i]=0;
14 for(j=0;j<=y;j++)
15 c[1][j]=0;
16
17 for(i=1;i<=x;i++)
18 {
19 for(j=1;j<=y;j++)
20 {
21 if(aa[i-1] == bb[j-1]) c[1][j] = c[0][j-1]+1;
22 else c[1][j]=Max(c[1][j-1],c[0][j]);
23 }
24 //为c重新赋值
25 for(int s=0;s<=y;s++)
26 c[0][s]=c[1][s];
27 c[1][0]=0;
28 }
29 }
30 int main()
31 {
32 char a[M],b[M];
33 int L1,L2;
34 while(cin>>a>>b)
35 {
36 L1=strlen(a);
37 L2=strlen(b);
38 LCD(a,b,L1,L2);
39 cout<<c[0][L2]<<endl;
40 }
41 return 0;
42 }
43
44 #include"iostream"
45 #define M 1000 //适合数据量小的字符串，那么字符串长度过大时又如何处理？!
46 using namespace std;
47 int c[M][M];
48 int Max(int a ,int b)
49 {
50 return a>b?a:b;
51 }
52 void LCD(char aa[], char bb[], int x, int y) //核心
53 {
54 int i,j;
55 for(i=0;i<=x;i++)
56 c[i][0]=0;
57 for(j=0;j<=y;j++)
58 c[0][j]=0;
59
60 for(i=1;i<=x;i++)
61 for(j=1;j<=y;j++)
62 {
63 if(aa[i-1] == bb[j-1]) c[i][j] =c[i-1][j-1]+1; //将前一行前一列的值+1(即对角线上前一个点加1，目的是保证了所找到的字符串是最大的)
64 else c[i][j]=Max(c[i][j-1],c[i-1][j]); //在不相等的情况下，将同列的前一行或者同行的前一列中选一个最大数赋给c[i][j]，从而保证了下一次循环可以依然按照同样的方式进行;
65 }
66 }
67 int main()
68 {
69 char a[M],b[M];
70 int L1,L2;
71 while(cin>>a>>b)
72 {
73 L1=strlen(a);
74 L2=strlen(b);
75 LCD(a,b,L1,L2);
76 cout<<c[L1][L2]<<endl;
77 }
78 return 0;
79 } http://poj.org/problem?id=1458