View Code #include < stdio.h > #include < string .h > #define M 1010 int c[M][M]; int f[M][M]; int min( int a, int b, int c){ int z = (a < b) ? a:b; if (z < c) return z; else return c;} int Max( int a , int b){ return a > b ? a:b;} void LCS( char aa[], char bb[], int x, int y){ int i,j; for (i = 0 ;i <= x;i ++ ) c[i][ 0 ] = 0 ; for (j = 0 ;j <= y;j ++ )c[ 0 ][j] = 0 ; for (i = 1 ;i <= x;i ++ ) for (j = 1 ;j <= y;j ++ ) { if (aa[i - 1 ] == bb[j - 1 ]) c[i][j] = c[i - 1 ][j - 1 ] + 1 ; else c[i][j] = Max(c[i][j - 1 ],c[i - 1 ][j]); }} int main(){ char a[M],b[M]; int L1,L2; int t; int k = 0 ;scanf( " %d " , & t); while (t -- ){ scanf( " %s %s " ,a,b); L1 = strlen(a);L2 = strlen(b);LCS(a,b,L1,L2); int xx = c[L1][L2]; int ans = 0 ; int i,j; f[ 0 ][ 0 ] = 0 ; for (i = 0 ;i <= L1;i ++ ) f[i][ 0 ] = i; for (j = 0 ;j <= L2;j ++ ) f[ 0 ][j] = j; for (i = 1 ;i <= L1;i ++ ) for (j = 1 ;j <= L2;j ++ ) { if (a[i - 1 ] == b[j - 1 ]) // 转移方程 f[i][j] = f[i - 1 ][j - 1 ]; else f[i][j] = min(f[i - 1 ][j - 1 ] + 1 ,f[i - 1 ][j] + 1 ,f[i][j - 1 ] + 1 ); } printf( " Case %d: LCS=%d EditStep=%d\n " , ++ k,xx,f[L1][L2]);} return 0 ;}