Common Subsequence（最长公共子序列+动态规划）hdu1159 经典_c程序common subsequence

Common Subsequence

  
  

   
   abcfbc abfcab
programming contest 
abcd mnp
  
  

  
  

   
   4
2
0
  
  

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1159

题意：求两个字符串的最长公共子串。

思路：动态规划。

最长公共子序列是一个很经典的动态规划问题，最近正在学习动态规划，所以拿来这里再整理一下。

这个问题在《算法导论》中作为讲动态规划算法的例题出现。

动态规划，众所周知，第一步就是找子问题，也就是把一个大的问题分解成子问题。这里我们设两个字符串A、B，A = "a0, a1, a2, ..., am-1"，B = "b0, b1, b2, ..., bn-1"。

（1）如果am-1 == bn-1，则当前最长公共子序列为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列与am-1的和。长度为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列的长度+1。

（2）如果am-1 != bn-1，则最长公共子序列为max（"a0, a1, ..., am-2"与"b0, b1, ..., bn-1"的公共子序列，"a0, a1, ..., am-1"与"b0, b1, ..., bn-2"的公共子序列）

如果上述描述用数学公式表示，则引入一个二维数组c[][]，其中c[i][j]记录X[i]与Y[j]的LCS长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，即，搜索方向。

这样我们可以总结出该问题的递归形式表达：

按照动态规划的思想，对问题的求解，其实就是对子问题自底向上的计算过程。这里，计算c[i][j]时，c[i-1][j-1]、c[i-1][j]、c[i][j-1]已经计算出来了，这样，我们可以根据X[i]与Y[j]的取值，按照上面的递推，求出c[i][j]，同时把路径记录在b[i][j]中（路径只有3中方向：左上、左、上，如下图）。

计算c[][]矩阵的时间复杂度是O(m*n)；根据b[][]矩阵寻找最长公共子序列的过程，由于每次调用至少向上或向左移动一步，这样最多需要（m+n）次就会i = 0或j = 0，也就是算法时间复杂度为O(m+n)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int map[10005][10005];
string str1,str2;
int len1,len2;
//最长公共子序列
/***
递归解法：
             0                            if(i==0||j==0);
map[i][j] =  map[i-1][j-1]                if(i>0&&j>0&&str1[i]==str2[j])
             max(map[i-1][j],map[i][j-1]) if(i>0&&j>0&&str1[i]!=str2[j])
*/
/*****递归超时了！
int LCS(int x,int y)
{
    if(x<0||y<0) return 0;
    if( str1[x]==str2[y])  return LCS(x-1,y-1)+1;
    else  return max(LCS(x-1,y),LCS(x,y-1));
}*/
int main()
{
    while(cin>>str1>>str2)
    {
        len1=str1.length()-1;
        len2=str2.length()-1;
 
 //       printf("%d\n",LCS(len1,len2));
        /***非递归解法LCS*/
        for(int i=0;i<=len1+1;i++)
        {
            for(int j=0;j<=len2+1;j++)
            {
                if(i==0||j==0) {map[i][j]=0;continue;}
                if(str1[i-1]==str2[j-1])
                {
                    map[i][j]=map[i-1][j-1]+1;
                }
                else
                {
                    map[i][j]=max(map[i-1][j],map[i][j-1]);
                }
            }
        }
        printf("%d\n",map[len1+1][len2+1]);
    }
    return 0;
}

还有一种优化空间的方法，利用滚动数组！这里也附上代码。在不需要记录路径的时候很好用！

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int map[2][10005];
string str1,str2;
int len1,len2;
//最长公共子序列
 
int LCS(int x,int y)
{
    for(int i=0;i<=x;i++)
    {
        for(int j=0;j<=y+1;j++)
        {
            if(i==0||j==0) {map[i%2][j]=0;continue;}
            if(str1[i-1]==str2[j-1])
            {
                map[i%2][j]=map[(i-1)%2][j-1]+1;
            }
            else
            {
                map[i%2][j]=max(map[(i-1)%2][j],map[i%2][j-1]);
            }
        }
    }
 
}
int main()
{
    while(cin>>str1>>str2)
    {
        len1=str1.length();
        len2=str2.length();
        LCS(len1,len2);
        printf("%d\n",map[len1%2][len2]);
    }
    return 0;
}