1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 int main()
7 {
8 char s1[501];
9 char s2[501];
10 while ( scanf ( "%s",s1 ) != EOF ){
11 scanf ( "%s",s2 );
12 int s3[500][500];
13 int l1,l2;
14 l1 = strlen( s1 );
15 l2 = strlen( s2 );
16 for ( int i = 0; i != l1+1; ++i )
17 for ( int j = 0; j != l2 + 1; ++j )
18 s3[i][j] = 0;
19 int max1 = 0;
20 for ( int i = 0; i != l1; ++i )
21 for ( int j = 0; j != l2; ++j )
22 {
23 if ( s1[i] == s2[j] )
24 {
25 s3[i+1][j+1] = s3[i][j] + 1;
26 if ( s3[i+1][j+1] > max1 )
27 max1 = s3[i+1][j+1];
28 }
29 else
30 s3[i+1][j+1] = max (s3[i+1][j], s3[i][j+1]);
31 }
32 printf ( "%d\n",max1 );
33 }
34 return 0;
35 }
36
这题其实不难,思想很简单,就是记录下前一个字母的最长子序列!
哈哈~~虽然参考书后还是相比较久,但总算会了!