文档章节

IT笔面试之最长公共子序列

Taisuke
 Taisuke
发布于 2014/09/02 20:24
字数 405
阅读 225
收藏 9

先介绍LCS问题的性质:记Xm={x0, x1,…xm-1}Yn={y0,y1,…,yn-1}为两个字符串,而Zk={z0,z1,…zk-1}是它们的LCS,则:

1.       如果xm-1=yn-1,那么zk-1=xm-1=yn-1,并且Zk-1Xm-1Yn-1LCS
2.       如果xm-1≠yn-1,那么当zk-1≠xm-1ZXm-1YLCS
3.       如果xm-1≠yn-1,那么当zk-1≠yn-1ZYn-1XLCS

公式: 

            0                                if  i<0 or j<0
c[i,j]=       c[i-1,j-1]+1                     if  i,j>=0 and xi=xj
            max(c[i,j-1],c[i-1,j])            if  i,j>=0 and xi≠xj
 

注意与最长公共子串的区别:字串是连续的,子序列可不连续。

http://my.oschina.net/gaosheng/blog/308853

 
#include <cstring>
#include <cstdio>
#define M 1010
 
int LCS(char* str1, char* str2)
{
    if(!str1 || !str2)
        return 0;
 
    int length_1 = strlen(str1);
    int length_2 = strlen(str2);
 
    if(!length_1 || !length_2)
        return 0;
 
    int m[length_1+1][length_2+1];
 
    //初始化边界,过滤掉0的情况
    for (int i = 0; i <= length_1; i++)
        m[i][0] = 0;
 
 
    for (int j = 0; j <= length_2; j++)
        m[0][j] = 0;
 
 
    //填充矩阵
    for (int i = 1; i <= length_1; i++)
    {
        for (int j = 1; j <= length_2; j++)
        {
            //相等的情况
            if (str1[i - 1] == str2[j - 1])
                m[i][j] = m[i - 1][j - 1] + 1;
            else
            {
                //比较“左边”和“上边“,根据其max来填充
                if (m[i - 1][j] >= m[i][j - 1])
                    m[i][j] = m[i - 1][j];
                else
                    m[i][j] = m[i][j - 1];
            }
        }
    }
    return m[length_1][length_2];
}
 
int main()
{
    char str1[M],str2[M];
    memset(str1,0,sizeof(M));
    memset(str2,0,sizeof(M));
 
    printf("请输入字符串str1:");
    scanf("%s", str1);
 
    printf("请输入字符串str2:");
    scanf("%s", str2);
 
    printf("%d\n",LCS(str1,str2));
    return 0;
}


© 著作权归作者所有

Taisuke
粉丝 7
博文 36
码字总数 14463
作品 0
济南
程序员
私信 提问
最长公共子序列(LCS)

最长公共子序列,即Longest Common Subsequence,LCS。一个序列S任意删除若干个字符得到新序列T,则T叫做S的子序列;两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序...

klaus丶
2016/02/24
49
0
【动态规划】基础,最长公共子序列问题(LCS)

正文之前 囚徒健身初期感觉还是很温和的,练习起来不吃力,而且对身体的负荷也很小,还是不错的,推荐大家也学习下。。进入正题,最长公共子序列问题 正文 (1)子序列: 一个序列,中任意删除...

HustWolf
2018/07/23
0
0
python实现最长公共子序列的求解

(待完善...) 最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。 1.找出最优解的性质,并刻划其结构特征 序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么...

勉旃
2018/09/03
0
0
算法与数据结构(二):动态规划(DP)总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89388883 1. 最长公共子序列 题目描...

dby_freedom
04/21
0
0
删除部分字符使其变成回文串问题——最长公共子序列LCS问题

先要搞明白:最长公共子串和最长公共子序列的区别。 最长公共子串(Longest Common Substirng):连续 最长公共子序列(Longest Common Subsequence,LCS):不必连续 题目:给定一个字符串s...

牧师-Panda
2016/09/10
724
0

没有更多内容

加载失败,请刷新页面

加载更多

IT兄弟连 HTML5教程 HTML5表单 小结及习题

小结 HTML表单提交的方法有get方法和post方法,get方法的作用是从指定的资源请求数据,post方法的作用是向指定的资源提交要被处理的数据。HTML表单一直都是Web的核心技术之一,有了它我们才能...

老码农的一亩三分地
26分钟前
14
0
向maven工程中导入自己封装好的jar包方法

1.打开cmd窗口 输入并执行:mvn install:install-file -DgroupId=com.test   -DartifactId=ptest -Dversion=0.1  -Dfile=E:\test\test-0.1.0.jar    -Dpackaging=jar注:Dgr......

gantaos
28分钟前
3
0
【jQuery基础学习】09 jQuery与前端(这章很水)

本文转载于:专业的前端网站➨【jQuery基础学习】09 jQuery与前端(这章很水) 这章主要是将如何将jQuery应用到网站中,或者说其实就是一些前端知识,对于我这种后端程序来说其实还是蛮有用的...

前端老手
39分钟前
11
0
深度科技与金山云完成兼容互认证 共同促进我国软件生态发展

近日,深度科技与金山云完成兼容互认证工作,经双方共同严格测试,深度操作系统ARM服务器版软件V15与金山云分布式数据库软件DragonBase V1.0相互兼容、稳定运行,可以为企业级应用提供全面保...

后浪涛涛
40分钟前
8
0
Less导入选项

Less 提供了CSS @import CSS规则的几个扩展,以提供更多的灵活性来处理外部文件。 语法: @import (keyword) "filename"; 以下是导入指令的相关详情: reference,使用较少的文件但不输出。 ...

凌兮洛
56分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部