开发者社区> 技术小甜> 正文

公共子序列与公共子串问题

简介:
+关注继续查看

1、公共子序列问题

网上有很多关于公共子序列问题,说的大同小异,看了很多不明白,很多都是晦涩难懂,这里分享一个连接,个人觉得讲述的比较明白,易懂。

http://blog.csdn.net/v_july_v/article/details/6695482

我这里也简单的把自己的理解说一下,求公共子序列问题是一个非常常见的问题,最差的方法就是暴力匹配,暴力匹配算法第一步求去短字符串的所有序列组合,然后从长到短一个一个的去匹配时候有公共序列相同,即使使用了这样的剪枝,该算法效率任然很低。

比较受人青睐的算法当然莫过于动态规划了,动态规划的核心是找到转移方程。把复杂的问题通过转移方程转移到子问题。

  • 动态规划算法

    事实上,最长公共子序列问题也有最优子结构性质。

记:

Xi=﹤x1,⋯,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀)

Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀)

假定Z=﹤z1,⋯,zk﹥∈LCS(X , Y)。

  • xm=yn(最后一个字符相同),则不难用反证法证明:该字符必是X与Y的任一最长公共子序列Z(设长度为k)的最后一个字符,即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时,问题化归成求Xm-1与Yn-1的LCS(LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1)。

  • xm≠yn,则亦不难用反证法证明:要么Z∈LCS(Xm-1, Y),要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立,若zk≠xm则有Z∈LCS(Xm-1 , Y),类似的,若zk≠yn 则有Z∈LCS(X , Yn-1)。此时,问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为:max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。

    由于上述当xm≠yn的情况中,求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度,这两个问题不是相互独立的:两者都需要求LCS(Xm-1,Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS,故问题具有最优子结构性质考虑用动态规划法。

    也就是说,解决这个LCS问题,你要求三个方面的东西:1、LCS(Xm-1,Yn-1)+1;2、LCS(Xm-1,Y),LCS(X,Yn-1);3、max{LCS(Xm-1,Y),LCS(X,Yn-1)}

所以解决这个问题的动态转移方程即:

if xm==yn  LCS(Xm,Yn)= LCS(Xm-1,Yn-1)+1;
if xm!=yn LCS(Xm,Yn)=  max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)};

代码如下:

复制代码
#include <stdio.h>
#include <string.h>

/*
c[i][j]存储的是字串1到i位置,字串2到j位置时公共子序列的最大长度

if str1[i] == str2[j]    c[i][j] = c[i-1][j-1]+1;
if str1[i] != str2[j]    c[i][j] = max{c[i-1][j],c[i][j-1]}
*/
int lcs(char *str1,char *str2,int len1,int len2,int c[100][100])
{
    if (str1 == NULL || str2 ==NULL)
    {
        return -1;//输入字符串错误
    }
    //初始化记录dp的二维数组
    for (int i = 0; i <= len1; i++)
    {
        for (int j = 0; j <= len2; j++)
        {
            c[i][j] = 0;
        }
    }
    //dp运算
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if(str1[i-1] == str2[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
            }
            else {
                c[i][j] = c[i-1][j]>c[i][j-1]?c[i-1][j]:c[i][j-1];
            }
        }
    }
    //打印出dp数组存储的内容
    for (int i = 0; i <= len1; i++)
    {
        for (int j = 0; j <= len2; j++)
        {
            printf("%d ",c[i][j]);
        }
        printf("\n");
    }

    //打印出公共子序列
    char str[100]={0};
    int index = c[len1][len2]-1;
    for (int i = len1,j = len2; i>0&&j>0;)
    {
        if(str1[i-1] == str2[j-1])
        {
            str[index--] = str1[i-1];
            i--;
            j--;
        }
        else 
        {
            if(c[i][j-1]>c[i-1][j])
            {
                j--;
            }else 
            {
                i--;
            }
        }
    }
    printf("公共子序列为:%s\n",str);
    return c[len1][len2];
}


int main(int argc, char **argv)
{
    char str1[] = {"ABCBDAB"};
    char str2[] = {"BDCABA"};
    int c[100][100];
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int num = lcs(str1,str2,len1,len2,c);
    printf("公共子序列的长度:%d\n",num);
    return 0;
}
复制代码

 运行结果

 

2、最大公共子串

首先区分下公共字串和公共子序列的区别,公共子序列是在整个字符串中只要按照顺序可以不用连续的,但是公共子串是指必须连续的字符串,举个例子

 

ABCBDAB
BDCABA

公共子序列是  BCBA

公共字串是  AB

求公共字串比公共子序列稍微简单了一些,如果上边所述,公共子串也可以用暴力匹配方法,求出较短的字符串的所有子串,然后可以从长到短利用kmp字符串匹配算法求出公共子串,同时还添加了剪枝,但是字样的暴力匹配效率始终是比较差的,最好的方法还是使用动态规划。

根据上边公共子序列动态规划的方法分析,其实我们可以发现公共子串和公共子序列非常类似

只是在状态转移方程是稍有不同,

   事实上,最长公共子串问题也有最优子结构性质。

记:

Xi=﹤x1,⋯,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀)

Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀)

假定Z=﹤z1,⋯,zk﹥∈LCS(X , Y)。

  • xm=yn(最后一个字符相同),则不难用反证法证明:该字符必是X与Y的任一最长公共子串Z(设长度为k)的最后一个字符,即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子串。此时,问题化归成求Xm-1与Yn-1的LCS(LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1)。

  • 重要的是这里的不同:
    • xm≠yn,由于zk≠xm与zk≠yn 那么说明之前相同的字符串也不能连接起来,此时的LCS(X,Y) 的长度回归到0重新找最长的公共子串。

所以:关于最长公共子串的动态转移方程为:

if xm==yn  LCS(Xm,Yn)= LCS(Xm-1,Yn-1)+1;
if xm!=yn LCS(Xm,Yn)=  0;

代码如下:

复制代码
#include <stdio.h>
#include <string.h>

/*
c[i][j]存储的是字串1到i位置,字串2到j位置时公共字串的最大长度

if str1[i] == str2[j]    c[i][j] = c[i-1][j-1]+1;
if str1[i] != str2[j]    c[i][j] = 0
*/
int lcs(char *str1,char *str2,int len1,int len2,int c[100][100])
{
    if (str1 == NULL || str2 ==NULL)
    {
        return -1;//输入字符串错误
    }
    //初始化记录dp的二维数组
    for (int i = 0; i <= len1; i++)
    {
        for (int j = 0; j <= len2; j++)
        {
            c[i][j] = 0;
        }
    }
    //dp运算
    int max = -1;
    int col=0,row=0;
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if(str1[i-1] == str2[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
                if(c[i][j]>max)
                {
                    row = i;
                    col = j;
                    max = c[i][j];
                }
            }
            else {
                c[i][j] = 0;
            }
        }
    }
    //打印出dp数组存储的内容
    for (int i = 0; i <= len1; i++)
    {
        for (int j = 0; j <= len2; j++)
        {
            printf("%d ",c[i][j]);
        }
        printf("\n");
    }
    
    //打印出公共子串
    printf("最长公共子串:");
    for (int i = row-max; i<row;i++)
    {
        printf("%c",str1[i]);
    }
    printf("\n");
    return max;
}


int main(int argc, char **argv)
{
    char str1[] = {"ABCBDAB"};
    char str2[] = {"BDCABA"};
    int c[100][100];
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    printf("字符串1:%s\n",str1);
    printf("字符串2:%s\n",str2);
    int num = lcs(str1,str2,len1,len2,c);
    printf("公共子序列的长度:%d\n",num);
    return 0;
}
复制代码

结果:













本文转自NewPanderKing51CTO博客,原文链接:http://www.cnblogs.com/newpanderking/p/3946159.html ,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【算法与数据结构】最大子序列和问题
(转载请注明出处:http://blog.csdn.net/buptgshengod) 1.题目      给定一个数字序列,其中有正有负,确定最大子序列和。用穷举法最好的结果也是时间复杂度O(n²)。后来看到一个聪明的方法,直接使时间复杂度变为O(n)。 2.解法 (1)穷举法        把所有序列都算出来找到最大的。 /* 最大序列和问题的求解,一组数列有正有负
748 0
最大子序列和问题【转】
发现这个文章写的很好,所以转载了,文章来源:http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html 问题描述: 输入一组整数,求出这组数字子序列和中最大值。
509 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
19980 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23523 0
动态规划法(十)最长公共子序列(LCS)问题
问题介绍   给定一个序列X=X=X=,另一个序列Z=Z=Z=满足如下条件时称为X的子序列:存在一个严格递增的X的下标序列,对所有的j=1,2,...,kj=1,2,...,kj=1,2,...,k满足xij=zj.xij=zj.x_{i_j}=z_j.   给定两个序列XXX和YYY,如果ZZZ同时是XXX和YYY的子序列,则称ZZZ是XXX和YYY的公共子序列。
8024 0
【刷穿 LeetCode】446. 等差数列划分 II - 子序列 :详解如何分析「序列 DP」问题
【刷穿 LeetCode】446. 等差数列划分 II - 子序列 :详解如何分析「序列 DP」问题
17 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
12967 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
20879 0
+关注
10140
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载