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 }