#include <iostream>
#include <string.h>
#define N 1005
using namespace std ;
char s1[N],s2[N];
int dp[N][N],ans,len1,len2;
int max(int a,int b)
{ return a>b ? a : b ; }
int f(int x,int y)
{
if ( x==0 || y==0 ) return dp[x][y]=0;
else if (s1[x-1]!=s2[y-1]) return dp[x][y]=max( f(x-1,y),f(x,y-1));
else return dp[x][y]=f(x-1,y-1)+1;
}
int main()
{
int n,i,j ;
while ( cin>>s1>>s2 )
{ len1=strlen(s1); len2=strlen(s2);
f(len1,len2);
ans=0;
for (i=0; i<=len1; i++)
for (j=0; j<=len2; j++)
if ( ans<dp[i][j] ) ans=dp[i][j] ;
cout << ans << endl ;
}
return 0 ;
}
1458 poj--zoj 1733---------------递归,布布扣,bubuko.com
1458 poj--zoj 1733---------------递归
原文：http://www.cnblogs.com/2014acm/p/3907979.html