我们用Ax表示序列A的连续前x项构成的子序列，即Ax= a1,a2,……ax, By= b1,b2,……by, 我们用LCS(x, y)表示它们的最长公共子序列长度，那原问题等价于求LCS(m,n)。为了方便我们用L(x, y)表示Ax和By的一个最长公共子序列。

让我们来看看如何求LCS(x, y)。我们令x表示子序列,考虑最后一项

第（）种情况：Ax ＝ By

那么它们L(Ax, By)的最后一项一定是这个元素！

为什么呢？为了方便，我们令t=Ax=By, 我们用反证法：假设L(x,y)最后一项不是t，

则要么L(x,y)为空序列（别忘了这个），要么L(x,y)的最后一项是Aa＝Bb ≠ t, 且显然有a<x,b<y。无论是哪种情况我们都可以把t接到这个L(x,y)后面,从而得到一个更长的公共子序列。矛盾！

如果我们从序列Ax中删掉最后一项ax得到Ax-,从序列By中也删掉最后一项by得到By-，(多说一句角标为0时，认为子序列是空序列)，则我们从L(x,y)也删掉最后一项t得到的序列是L(x – , y - )。为什么呢？和上面的道理相同，如果得到的序列不是L(x - , y - )，则它一定比L(x - , y - )短，那么它后面接上元素t得到的子序列L(x,y)也比L(x - , y - )接上元素t得到的子序列短，这与L(x, y)是最长公共子序列矛盾。

因此L(x,y)=L(x-,y-)最后接上元素t，也就是说：

LCS(Ax, By) = LCS(x - , y - ) + 

第（）种情况：Ax ≠ By

仍然设t=L(Ax,By)的最后一个字符,或者L(Ax,By)是空序列（这时t是未定义值不等于任何值）。

则t≠Ax和t≠By至少有一个成立，因为t不能同时等于两个不同的值嘛！

（2.1） 如果t≠Ax，则有L(x,y)=L(x-,y)，因为根本没Ax的事嘛。

       也就是说：LCS(x,y) = LCS(x – , y)

（2.2） 如果t≠By,同理有L(x,y)= L(x,y-)。

       也就是说：LCS(x,y) = LCS(x, y – )

可是，我们事先并不知道t，由定义，我们取最大的一个，因此这种情况下,有LCS(x,y)=max(LCS(x–,y),LCS(x,y–))。

看看目前我们已经得到了什么结论：

LCS(x,y) =

    () LCS(x - ,y - ) +  如果Ax ＝ By

    () max(LCS(x – , y) , LCS(x, y – )) 如果Ax ≠ By

这是一个显然的递推式，光有递推可不行，初值是什么呢？

显然，一个空序列和任何序列的最长公共子序列都是空序列！所以我们有:

LCS(x,y) =

    () LCS(x - ,y - ) +      如果Ax ＝ By

    () max(LCS(x – , y) , LCS(x, y – ))     如果Ax ≠ By

    ()      如果x=0或者y=

到此我们求出了计算最长公共子序列长度的递推公式。我们实际上计算了一个(n + )行(m + )列的表格（行是0..n，列是0..m)，也就这个二维度数组LCS(n,m)。

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 int LCSLength(char* str1, char* str2, int **b)

 {

     int i,j,length1,length2,len;

     length1 = strlen(str1);

     length2 = strlen(str2);

     //双指针的方法申请动态二维数组

     int **c = new int*[length1+]; //共有length1+1行

     for(i = ; i < length1+; i++)

         c[i] = new int[length2+];//共有length2+1列

     for(i = ; i < length1+; i++)

         c[i][]=;        //第0列都初始化为0

     for(j = ; j < length2+; j++)

         c[][j]=;        //第0行都初始化为0

     for(i = ; i < length1+; i++)

     {

         for(j = ; j < length2+; j++)

         {

             if(str1[i-]==str2[j-])//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素

             {

                 c[i][j]=c[i-][j-]+;

                 b[i][j]=;          //输出公共子串时的搜索方向

             }

             else if(c[i-][j]>c[i][j-])

             {

                 c[i][j]=c[i-][j];

                 b[i][j]=;

             }

             else

             {

                 c[i][j]=c[i][j-];

                 b[i][j]=-;

             }

         }

     }

     /*

     for(i= 0; i < length1+1; i++)

     {

     for(j = 0; j < length2+1; j++)

     printf("%d ",c[i][j]);

     printf("\n");

     }

     */

     len=c[length1][length2];

     for(i = ; i < length1+; i++)    //释放动态申请的二维数组

         delete[] c[i];

     delete[] c;

     return len;

 }

 void PrintLCS(int **b, char *str1, int i, int j)

 {

     if(i== || j==)

         return ;

     if(b[i][j]==)

     {

         PrintLCS(b, str1, i-, j-);//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串

         printf("%c",str1[i-]);//c[][]的第i行元素对应str1的第i-1个元素

     }

     else if(b[i][j]==)

         PrintLCS(b, str1, i-, j);

     else

         PrintLCS(b, str1, i, j-);

 }

 int main(void)

 {

     char str1[],str2[];

     int i,length1,length2,len;

     printf("请输入第一个字符串：");

     gets(str1);

     printf("请输入第二个字符串：");

     gets(str2);

     length1 = strlen(str1);

     length2 = strlen(str2);

     //双指针的方法申请动态二维数组

     int **b = new int*[length1+];

     for(i= ; i < length1+; i++)

         b[i] = new int[length2+];

     len=LCSLength(str1,str2,b);

     printf("最长公共子序列的长度为：%d\n",len);

     printf("最长公共子序列为：");

     PrintLCS(b,str1,length1,length2);

     printf("\n");

     for(i = ; i < length1+; i++)//释放动态申请的二维数组

         delete[] b[i];

     delete[] b;

     system("pause");

     return ;

 }

 #include <iostream>

 #include <cstring>

 using namespace std;

 char sz1[];

 char sz2[];

 int maxLen[][];

 int main()

 {

     int i,j,length1,length2,cur=;

     while( cin >> sz1 >> sz2 )

     {

         length1 = strlen( sz1);

         length2 = strlen( sz2);

         for( i=;i<; i++ ) maxLen[i][]=;

         for( j=;j<=length2;j++ ) maxLen[][j]=;

         cur=;

         for( i = ;i <= length1;i ++ )

         {

             cur ^= ;

             for( j = ; j <= length2; j ++ )

             {

                 if( sz1[i-] == sz2[j-] )

                     maxLen[cur][j] = maxLen[cur^][j-] + ;

                 else

                     maxLen[cur][j] = max(maxLen[cur][j-],maxLen[cur^][j]);

             }

         }

         cout << maxLen[cur][length2] << endl;

     }

     return ;

 }