[原]最长公共子序列

王良 18/02/03 22:58:15

何为最长公共子序列?百度百科定义如下:一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

首先,我们来介绍一下子串与子序列 的区别:子串是一个字符串中的连续字符的集合;子序列是一个字符串中任意字符的集合,不一定要连续。

然后,如何来求得最长公共子序列呢?最直接的一种方法就是暴力求解,通过比较两个字符串的所有子序列,得到公共子序列,最终得到长度最长的长度。然而这种方法的时间复杂度达到了O(2^n),可见这种方法耗时太长。

所以,我们需要一种更加高效的算法来解决,那就是动态规划。我们可以将求最长公共子序列分解为若干个子问题,即求str1的前i个字符str2的前j个字符的最长公共子序列,我们假设用maxLen( i, j )来表示。

那maxLen(i, j)怎么求呢?此时,可以分为两种情况:str1[ i - 1 ] == str2[ j - 1 ]str1[ i - 1 ] != str2[ j - 1 ](str1的第i个字符与str2的第j个字符是否相同,因为数组从str1[0]开始,所以为i-1)。

对于第一种str1[ i - 1 ] == str2[ j - 1 ]很好理解,因为两个字符序列的最后一个字符相同,所以同时去掉最后一个字符,此时长度就是maxLen(i-1, j-1),所以再加上最后一个相同的字符,就得到maxLen(i, j) = maxLen(i-1, j-1) + 1

1

对于第二种情况str1[ i - 1 ] != str2[ j - 1 ],因为两字符串的最后一个字符不相同,也就是说最后的字符不会同时属于公共子序列(否则的话就成了两子符相同的情况),因此可以分情况讨论,去掉其中一个,讨论剩余字符串的最长公共子序列,选择其中较大的一个作为公共子序列长度,即maxLen(i, j) = max( maxLen(i-1, j), maxLen(i, j-1) )。也就是先得出str1的左i-1个字符与str2当前子序列(前j个字符)的maxLen,再算出str1的当前子序列(前i个字符)与str2前j-1个字符的maxLen,把两者中较大的作为maxLen(i, j)

一个例题:
POJ 1458 Common Subsequence

代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

char str1[1000], str2[1000];
int maxLen[1000][1000];

int main() {
    freopen("input.txt", "r", stdin);
    while( cin >> str1 >> str2 ) {
        int len1 = strlen( str1 );
        int len2 = strlen( str2 );
        memset( maxLen, 0, sizeof( maxLen ) );

        for( int i = 1; i <= len1; i++ ) {
            for( int j = 1; j <= len2; j++ ) {
                if ( str1[i-1] == str2[j-1] ) {
                    maxLen[i][j] = maxLen[i-1][j-1] + 1;
                } else {
                    maxLen[i][j] = max( maxLen[i-1][j], maxLen[i][j-1] );
                }
            }
        }

        cout << maxLen[len1][len2] << endl;
    }

    return 0;
}
作者:liushall 发表于 2018/02/03 22:58:15 原文链接 http://blog.csdn.net/liushall/article/details/79250119
阅读:15