1 #include<stdio.h>
2 #include<algorithm>
3 #include<string.h>
4 using namespace std;
5 const int maxn = 305;
6 int dp[ maxn ][ maxn ];
7 char a[ maxn ],b[ maxn ];
8 int same( int i,int j ){
9 if( a[ i ]==b[ j ] ) return 1;
10 return 0;
11 }
12 int fmax( int i,int j,int k ){
13 if( i<j )i=j;
14 if( i<k )i=k;
15 return i;
16 }
17 int main(){
18 while( scanf("%s%s",a,b)!=EOF ){
19 int lena,lenb;
20 lena=strlen( a ),lenb=strlen( b );
21 for( int i=0;i<=lena;i++ ) dp[ i ][ 0 ]=0;
22 for( int i=0;i<=lenb;i++ ) dp[ 0 ][ i ]=0;
23 //memset( dp,0,sizeof(dp) );
24
25 for( int i=1;i<=lena;i++ ){
26 for( int j=1;j<=lenb;j++ ){
27 //if( same( i-1,j-1 )==1 ) dp[ i ][ j ]=dp[ i-1 ][ j-1 ]+1;
28 //else dp[ i ][ j ]=max( dp[ i-1 ][ j ],dp[ i ][ j-1 ] );
29 dp[ i ][ j ]=fmax( dp[ i-1 ][ j-1 ]+same( i-1,j-1 ),dp[ i-1 ][ j ],dp[ i ][ j-1 ] );
30 }
31 }
32 printf("%d\n",dp[ lena ][ lenb ] );
33 }
34 return 0;
35 }
View Code
