最长公共子序列(POJ1458)-白红宇

题目链接：http://poj.org/problem?id=1458

题目大意：给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

输入有若干行，每行是两个字符串。对每一行输入的两个字符串，输出最长公共子串的长度。

Sample Input

abcfbc abfcab

programming contest

abcd mnp

Sample Output

算法分析

参考1：北大郭炜老师mooc课程

参考2：http://blog.csdn.net/u013480600/article/details/40741333

参考3：http://blog.csdn.net/lz161530245/article/details/76943991

输入两个串s1,s2,

设MaxLen(i,j)表示:s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算）

MaxLen(i,j) 就是本题的“状态”

假定 len1 = strlen(s1),len2 = strlen(s2）

那么题目就是要求 MaxLen(len1,len2)

显然：

MaxLen(n,0) = 0 ( n= 0…len1）

MaxLen(0,n) = 0 ( n=0…len2）

递推公式：

if(s1[i-1] == s2[j-1]) //s1的最左边字符是s1[0]

MaxLen(i,j) = MaxLen(i-1,j-1) + 1;

else

MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );

时间复杂度O(mn),其中m,n是两个字串长度。

关于证明，可以阅读和的证明过程。大概过程记录如下：

我们用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表示子序列,考虑最后一项第（1）种情况：Ax ＝ By那么它们L(Ax, By)的最后一项一定是这个元素！为什么呢？为了方便，我们令t=Ax=By, 我们用反证法：假设L(x,y)最后一项不是t，则要么L(x,y)为空序列（别忘了这个），要么L(x,y)的最后一项是Aa＝Bb ≠ t, 且显然有a

证明过程

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 char sz1[5005]; 5 char sz2[5005]; 6 int maxLen[5005][5005]; 7 int main() 8 { 9     while( cin >> sz1 >> sz2 ) 10     {11         int length1 = strlen( sz1);12         int length2 = strlen( sz2);13         int nTmp;14         int i,j;15         for( i = 0;i <= length1; i ++ ) maxLen[i][0] = 0;16         for( j = 0;j <= length2; j ++ ) maxLen[0][j] = 0;17         for( i = 1;i <= length1;i ++ ) 18         {19             for( j = 1; j <= length2; j ++ ) 20             {21                 if( sz1[i-1] == sz2[j-1] )22                     maxLen[i][j] = maxLen[i-1][j-1] + 1;23                 else24                     maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);25             }26         }27         cout << maxLen[length1][length2] << endl;28     }29     return 0;30 }

上面的题目并没有要求输出最长的公共子序列。假如要输出最长公共子序列，可以阅读的代码：（也可以暂时跳过，本文末尾有代码实现。）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 int LCSLength(char* str1, char* str2, int **b) 5 { 6     int i,j,length1,length2,len; 7     length1 = strlen(str1); 8     length2 = strlen(str2); 9 10     //双指针的方法申请动态二维数组11     int **c = new int*[length1+1]; //共有length1+1行12     for(i = 0; i < length1+1; i++)13         c[i] = new int[length2+1];//共有length2+1列14 15     for(i = 0; i < length1+1; i++)16         c[i][0]=0;        //第0列都初始化为017     for(j = 0; j < length2+1; j++)18         c[0][j]=0;        //第0行都初始化为019 20     for(i = 1; i < length1+1; i++)21     {22         for(j = 1; j < length2+1; j++)23         {24             if(str1[i-1]==str2[j-1])//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素25             {26                 c[i][j]=c[i-1][j-1]+1;27                 b[i][j]=0;          //输出公共子串时的搜索方向28             }29             else if(c[i-1][j]>c[i][j-1])30             {31                 c[i][j]=c[i-1][j];32                 b[i][j]=1;33             }34             else35             {36                 c[i][j]=c[i][j-1];37                 b[i][j]=-1;38             }39         }40     }41     /*42     for(i= 0; i < length1+1; i++)43     {44     for(j = 0; j < length2+1; j++)45     printf("%d ",c[i][j]);46     printf("\n");47     }48     */49     len=c[length1][length2];50     for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组51         delete[] c[i];52     delete[] c;53     return len;54 }55 void PrintLCS(int **b, char *str1, int i, int j)56 {57     if(i==0 || j==0)58         return ;59     if(b[i][j]==0)60     {61         PrintLCS(b, str1, i-1, j-1);//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串62         printf("%c",str1[i-1]);//c[][]的第i行元素对应str1的第i-1个元素63     }64     else if(b[i][j]==1)65         PrintLCS(b, str1, i-1, j);66     else67         PrintLCS(b, str1, i, j-1);68 }69 70 int main(void)71 {72     char str1[100],str2[100];73     int i,length1,length2,len;74     printf("请输入第一个字符串：");75     gets(str1);76     printf("请输入第二个字符串：");77     gets(str2);78     length1 = strlen(str1);79     length2 = strlen(str2);80     //双指针的方法申请动态二维数组81     int **b = new int*[length1+1];82     for(i= 0; i < length1+1; i++)83         b[i] = new int[length2+1];84     len=LCSLength(str1,str2,b);85     printf("最长公共子序列的长度为：%d\n",len);86     printf("最长公共子序列为：");87     PrintLCS(b,str1,length1,length2);88     printf("\n");89     for(i = 0; i < length1+1; i++)//释放动态申请的二维数组90         delete[] b[i];91     delete[] b;92     system("pause");93     return 0;94 }

求最长公共子序列长度并输出最长公共子序列

查找并输出最长公共子序列也可以参考https://wenku.baidu.com/view/7e96c94f2b160b4e767fcfc9.html

空间上的优化：

观察上面算法中的关键代码：

for( i = 1;i <= length1;i ++ ) {    for( j = 1; j <= length2; j ++ )     {        if( sz1[i-1] == sz2[j-1] ) maxLen[i][j] = maxLen[i-1][j-1] + 1;        else  maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);    }}

可以发现，计算maxLen数组第i行时用到的只有第i行与第i-1行。我们的目的是要计算maxLen[length1][length2]，所以，可以考虑只保存两行即可，也就是使用滚动数组只保存两行。

代码如下：（）

cur表示当前需要求的那一行的下标。

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 char sz1[5005]; 5 char sz2[5005]; 6 int maxLen[2][5005]; 7 int main() 8 { 9     int i,j,length1,length2,cur=0;10     11     while( cin >> sz1 >> sz2 ) 12     {13         length1 = strlen( sz1);14         length2 = strlen( sz2);15         for( i=0;i<2; i++ ) maxLen[i][0]=0;16         for( j=0;j<=length2;j++ ) maxLen[0][j]=0;17         cur=0;18         19         for( i = 1;i <= length1;i ++ ) 20         {21             cur ^= 1;22             for( j = 1; j <= length2; j ++ ) 23             {24                 if( sz1[i-1] == sz2[j-1] )25                     maxLen[cur][j] = maxLen[cur^1][j-1] + 1;26                 else27                     maxLen[cur][j] = max(maxLen[cur][j-1],maxLen[cur^1][j]);28             }29         }30         cout << maxLen[cur][length2] << endl;31     }32     return 0;33 }

View Code

下面修改一下代码寻找出一个最长公共子序列。

上面经过空间优化后，也只是寻找到了最长公共子序列的长度，那么如何得到一个最长公共子序列而仅仅不是简单的长度呢？其实我们离真正的答案只有一步之遥！

参考上图，我们建立一个二维数组ans[][]，在寻找最长公共子序列的长度时用ans[i][j]记录LCS（i，j）是如何来的（从左边、上边或是从左上），ans[i][j]等于1，2，3分别表示：

L(x,y) = L(x, y – 1)

L(x,y)= L(x – 1, y)

L(x,y) = L(x,- 1 y- 1)末尾接上Ax

当ans[i][j]等于3时字符串1的第i个字符（或字符串2的第j个字符，其实两者相同）肯定是最长公共子序列的一部分，要保留到temp[ ]中。所以从ans[][]右下角逆推即可求出temp[ ]，然后逆序输出temp[]即可。代码如下：

1 //51Nod动态规划教程例题 求最长公共子序列的长度并输出一个最长公共子序列 2 #include 
     
       3 #include 
      
        4 using namespace std; 5 #define maxN 5005 6 char sz1[maxN]; 7 char sz2[maxN]; 8 int maxLen[2][maxN]; 9 char ans[maxN][maxN]={
   0};10 11 void printLCS(int len1,int len2);//输出一个最长公共子序列 12 int main()13 {14     int i,j,length1,length2,cur=0;15     freopen("poj1458.in","r",stdin);16     while( cin >> sz1 >> sz2 ) 17     {18         memset(ans,0,sizeof(char)*maxN*maxN);19         length1 = strlen( sz1);20         length2 = strlen( sz2);21         for( i=0;i<2; i++ ) maxLen[i][0]=0;22         for( j=0;j<=length2;j++ ) maxLen[0][j]=0;23         cur=0;24         25         for( i = 1;i <= length1;i ++ ) 26         {27             cur ^= 1;28             for( j = 1; j <= length2; j ++ ) 29             {30                 if( sz1[i-1] == sz2[j-1] )31                 {32                     maxLen[cur][j] = maxLen[cur^1][j-1] + 1;33                     ans[i][j]=3;34                 }35                 else36                 {37                     //maxLen[cur][j] = max(maxLen[cur][j-1],maxLen[cur^1][j]);38                     if(maxLen[cur][j-1]>maxLen[cur^1][j])39                     {40                         maxLen[cur][j]=maxLen[cur][j-1];41                         ans[i][j]=1;42                     }43                     else44                     {45                         maxLen[cur][j]=maxLen[cur^1][j];46                         ans[i][j]=2;47                     }48                 }49             }50         }51         cout << maxLen[cur][length2] << endl;52         if(maxLen[cur][length2]>0) printLCS(length1,length2);53     }54     return 0;55 }56 void printLCS(int len1,int len2)//输出一个最长公共子序列57 {58     char temp[maxN];59     int i=len1,j=len2,k=0;60     while(ans[i][j]!=0)61     {62         if(ans[i][j]==3) { temp[k++]=sz1[i-1]; i--;j--; }63         else if(ans[i][j]==1)64         {65             j--;66         }67         else if(ans[i][j]==2)68         {69             i--;70         }71     }72     for(k--;k>=0;k--) printf("%c",temp[k]);73     printf("\n");74 }