最长公共子序列问题

问题描述:

求两个字符序列的公共最长子序列。


最长公共子串

在回到子序列问题之前,先来了解一下子串的问题。 例如,HISH和FISH两个字符序列的公共最长子串就是:ISH。很容易理解。


绘制网格

通过上一次背包问题的学习,给了我一些很重要的启示:

  • 每种动态规划解决方案都设计网格。
  • 动态规划可以帮助你在给定约束条件下找到最优解。
  • 问题可分解为彼此独立且离散的子问题时,就可以使用动态规划法来解决。

那么,要解决这个问题的网格长什么样呢?要确定这一点,你首先得回答:

  • 1.单元格中的值是什么?
  • 2.如何将这个问题划分成子问题?
  • 3.网格的坐标轴是什么?

在动态规划中,你要将某个指标最大化。在这个例子中,你要找出两个单词的最长公共子序列。hish和fish都包含的最长子序列是什么?hish和vista呢?这就是你要计算的值。

别忘了,单元格中的值通常就是你要优化的值。在这个例子中,这很可能是一个数字:两个字符串都包含的最长子串的长度。

如何把这个问题划分成子问题呢?你可能需要比较字符串:不是比较hish和fish,而是先比较his和fis。每个单元格都将包含着两个字符串的最长公共字符串的长度。或许有了一些线索:


填充网格

现在,你很清楚网格应是怎么样的。填充该网格的每个单元格时,该使用什么样的公式呢?由于你已经知道了答案——hish和fish的最长子序列为ish,所以可以作点弊。

几遍如此,你还是不能确定该使用什么样的公式。计算机科学家有时会开玩笑说,那就使用费曼算法(Feynman algorithm)。这个算法是以注明物理学家理查德·费曼命名的,其步骤如下:

实际上,根本没有找出计算公式的简单办法,你必须通过尝试才能找出管用的公式。有些算法并非精确的解决步骤,而只是帮助你理清思路的框架。


最终的网格

可以从其中总结出以下的规律:

实现这个公式的伪代码大概长这样:

if (chars1[i - 1] == chars2[j - 1]) {
    array[i][j] = array[i - 1][j - 1] + 1;
} else {
    array[i][j] = 0
}

需要注意的一点是,这个问题的最终答案并不一定在最后一个单元格中!对于前面的背包问题,最终答案总是在最后的单元格中。单对于LCS问题来说,答案为网格中最大的数字——它可能并不位于最后的单元格中。例如单词hish和vista的最长公共子串时,网格如下:


最长公共子序列

假设Alex不小心输入了fosh,那么它原本是想输入fish还是fort呢?我们使用最长子序列来比较它们。

最长公共个子串的长度相同,都包含两个字母。但fosh与fish更像。

这里比较的是最长公共子串,但其实应该比较最长子序列:两个单词中都有的序列包含的字数。如何计算最长公共子序列呢?

下面是用于计算fish和fosh的最长公共子序列的网格:

下面是填写这个网格的公式:

伪代码大概长这样:

if (chars1[i - 1] == chars2[j - 1]) {
    array[i][j] = array[i - 1][j - 1] + 1;
} else {
    array[i][j] = max{array[i -1][j] , array[i][j - 1] };
}

代码实现:

整个程序是从自己的算法学习程序中直接扒下来的,inputList保存的是从文本文件中一行一行读取到的数值,outputList保存的是要输出到文本文件中的数据。由于要输出,所以定义了一个boolean类型的isRowBig标志位,用来判断哪一个字符串的长度更长,然后获取更长的那个输出。虽然实现了代码,但是感觉自己写得很丑陋。

/**
 * 获取数据之后返回数据到输出Array中
 */
private void getResult() {
    // 获取数值
    int rowSize = inputList.get(0).length();
    int colSize = inputList.get(1).length();
    int[][] array = new int[rowSize + 1][colSize + 1];
    char[] chars1 = inputList.get(0).toCharArray();
    char[] chars2 = inputList.get(1).toCharArray();
    String temp = new String();

    // 初始化数组
    for (int i = 0; i < rowSize; i++) array[i][0] = 0;
    for (int i = 0; i < colSize; i++) array[0][i] = 0;

    // 填空
    boolean isRowBig = true;
    if (rowSize >= colSize) {
        isRowBig = true;
    } else {
        isRowBig = false;
    }   // 虽然实现了代码,但是感觉写得特别丑陋。
    for (int i = 1; i <= rowSize; i++) {
        for (int j = 1; j <= colSize; j++) {
            if (chars1[i - 1] == chars2[j - 1]) {
                array[i][j] = array[i - 1][j - 1] + 1;
                if (isRowBig) {
                    temp += chars2[j - 1];
                } else {
                    temp += chars1[i - 1];
                }   // end if:正确向temp中添加了字符
            } else if (array[i - 1][j] >= array[i][j - 1]) {
                array[i][j] = array[i - 1][j];
            } else {
                array[i][j] = array[i][j - 1];
            }
        }
    }   // end for:array和temp中已经保存了正确的数据

    outputList.add(temp);
 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

SAS里的平行世界 | 【SAS Says · 扩展篇】IML:1.入门

本节目录: 1. IML基本语句 2. 标量、向量与矩阵 (1)定义标量 (2)定义向量 (3)定义矩阵 3. 矩阵的元素运算 (1...

3936
来自专栏mathor

从暴力递归到动态规划

 动态规划没有那么难,但是很多老师在讲课的过程中讲的并不好,由此写下一篇文章记录学习过程

1981
来自专栏C/C++基础

Dijkstra算法求单源最短路径

在一个连通图中,从一个顶点到另一个顶点间可能存在多条路径,而每条路径的边数并不一定相同。如果是一个带权图,那么路径长度为路径上各边的权值的总和。两个顶点间路径长...

2141
来自专栏Python小屋

详解Python科学计算扩展库numpy中的矩阵运算(1)

首先解答上一篇文章中使用with关键字让你的Python代码更加Pythonic最后的习题,该题答案是False,原因在于内置函数sorted()的参数reve...

2854
来自专栏Petrichor的专栏

tensorflow编程: Layers (contrib)

min(max(features, 0), 6)。即对 tf.nn.relu 的优化,防止 relu过后 某些 极端值 依然 大于6

1972
来自专栏漫漫深度学习路

pytorch学习笔记(二):gradient

gradient 在BP的时候,pytorch是将Variable的梯度放在Variable对象中的,我们随时都可以使用Variable.grad得到对应Var...

2928
来自专栏专注研发

poj-3185-开关问题

牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。

993
来自专栏小樱的经验随笔

Vijos P1497 立体图【模拟】

立体图 描述 小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友讲解立体图,请你帮他画出立体图。 小渊有一块面积为m*n的...

3606
来自专栏机器学习算法工程师

经典算法题之Maximal Square

作者:叶 虎 编辑:邓高锦 Maximal Square是道非常有意思的算法题。它是一个典型的动态规划问题,同时也是2017京东面试题,2016华为机考题...

4099
来自专栏章鱼的慢慢技术路

《算法图解》第八章_贪婪算法_集合覆盖问题

4406

扫码关注云+社区