动态规划法(三)——最长公共子序列

问题描述

给定两个序列,求出它们的最长公共子序列。 如:序列X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a},则X和Y的最长公共子序列为{b,c,b,a}

  • 子序列:子序列为原序列的一个子集,并不要求连续,但要求子序列中元素的顺序和原序列元素的顺序一致。

定理

设两个序列分别是X={x1,x2……,xm},Y={y1,y2……,yn},它们的最长公共子序列为Z={z1,z2,……,zk}。

  1. 若xm=yn,则先求Xm-1和Yn-1的最长公共子序列,再在其尾部加上xm即可得Xm和Yn的最长公共子序列。
  2. 若xm!=yn,则必须分别求Xm、Yn-1和Xm-1、Yn的最长公共子序列,其中较长者就是Xm和Yn的最长公共子序列。

数据结构

  • c[i][j]: 用来记录Xi和Yj的最长公共子序列的长度。
  • s[i][j]: 用来标识Xi和Yi的最长公共子序列是由哪种情况得来:c[i][j-1]、c[i-1][j]、c[i][j]+1。 该数组能还原出最长公共子序列。

算法思路

1. 生成c数组和s数组所有元素

  1. 将c数组的第0行、第0列初始化为0;
  2. 从c数组的第一行、第一列开始,依次从左向右、从上到下填充元素值: a)若x[i]==y[j],则c[i][j]=c[i-1][j-1]+1,s[i][j]=1; b)若x[i]!=y[j],则分别计算c[i][j-1]、c[i-1][j],将大的那个作为c[i][j];并且,如果c[i-1][j]>=c[i][j-1],则s[i][j]=2;如果c[i-1][j]< c[i][j-1],则s[i][j]=3;

2. 根据s数组求得最长公共子序列

代码实现

private int[][] c;
private int[][] s;

1. 生成c数组和s数组所有元素

void LCSLength(String a, String b){
    // x和y的最前端分别加上0
    char[] x = ("0"+a).toCharArray();
    char[] y = ("0"+b).toCharArray();

    c = new int[x.length][y.length];
    s = new int[x.length][y.length];

    // 初始化c、s
    for( int i=0; i<x.length; i++ ){
        c[i][0] = 0;
    }
    for( int i=0; i<y.length; i++ ){
        c[0][i] = 0;
    }

    // 从上到下、从左到右填充c、s数组
    for( int i=1; i<x.length; i++ ){
        for( int j=1; j<y.length; j++ ){
            if( x[i]==y[j] ){
                c[i][j] = c[i-1][j-1]+1;
                s[i][j] = 1;
            }
            else if ( c[i-1][j] >= c[i][j-1] ){
                c[i][j] = c[i-1][j];
                s[i][j] = 2;
            }
            else {
                c[i][j] = c[i][j-1];
                s[i][j] = 3;
            }
        }
    }
}

2. 根据s数组求得最长公共子序列

StringBuilder sb = new StringBuilder();

void CLCS( int i, int j ){
    if ( i==0 || j==0 ) return;
    if ( s[i][j]==1 ) {
        CLCS( i-1,j-1 );
        sb.append( x[i] ); // 为了让公共子序列正序输出,因此需要在递归调用之后将x[i]添加至sb
    }
    else if ( s[i][j]==2 ){
        CLCS( i-1,j );
    }
    else {
        CLCS( i,j-1 );
    }
}

图示

  • 初始化c和s数组,将第0行、第0列都设为0:
  • 从第一行、第一列开始,依次从左到右、从上到下填充c和s数组:
  • 当c和s都填充完毕后,就可以根据s数组找到最长公共子序列 从s数组最右下角的元素开始: a)若s[i][j]==1,则找到一个字符,并继续比较左上角的元素; b)若s[i][j]==2,则继续比较上方的元素; c)s[i][j]==3,则继续比较左侧的元素。 d)直到i==0或j==0为止。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

60. 搜索插入位置二分查找__细节

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

513
来自专栏desperate633

Python爬虫之正则表达式入门正则表达式语法正则表达式实例ReMatch对象贪婪匹配和最小匹配

Re库是Python的标准库,主要用于字符串匹配 调用方式: import re

451
来自专栏Python小屋

Python版24点游戏

24点游戏是指随机选取4张扑克牌(不包括大小王),然后通过四则运算来构造表达式,如果表达式的值恰好等于24就赢一次。下面的代码定义了一个函数用来测试随机给定的4...

2916
来自专栏Python

while补充,字符串和数字的内置方法

一、while循环的补充 while True: name=input('please input your name: ') password...

1867
来自专栏数据结构与算法

27:单词翻转

27:单词翻转 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个句子(一行),将句子中的每一个单词翻转后输出。 输入只有一行,为一个...

3377
来自专栏和蔼的张星的图像处理专栏

算法1.排序二分查找及其变种

这个我也不知道能写多少,只是最近快放假了实在懒得看DSP了,而且卡在一个地方了,什么都不干又感觉心慌的很,所以又回头看看算法的东西。一些测试程序放在这里

722
来自专栏Linux驱动

快速排序(详解)

描述: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序...

1819
来自专栏运维技术迷

连仕彤博客[Python笔记] 判断0-9数字在字符串中出现的次数

要求 给定一些数字(0-9范围之间),判断数字在字符串中出现的次数。 例子的排序是依照算法的效率(时间复杂度)从低到高 例子1   # 定义数字 num = ...

3887
来自专栏企鹅号快讯

Python算法分享系列-查找,排序,递归

iTesting,爱测试,爱分享 沉寂了一段时间,继续学习。 算法这个系列我想分享很久了,奈何本身对算法不是特别了解,又找不到合适的载体来分享。 最近看了本有趣...

3866
来自专栏技术专栏

基本排序算法

● 基础 ● 编码简单,易于实现,是一些简单情景的首选 ● 在一些特殊情况下,简单的排序算法更有效 ● 简单的排序算法思想衍生出复杂的排序算法 ● 作为...

552

扫描关注云+社区