最长公共子序列/串问题

基础概念

• 字符串：S[0..n]，S是一个字符串，长度为n。S本质上是一个字符数组，数组的每个元素都是一个字符；
• 子序列：设T为S的一个子序列，则如果T[ti]和T[tj]为T的两个字符，ti<tj，那么T[ti]和T[tj]也都是S的字符，且对应的下标si<sj。举个例子，S为adbfhgs，那么abfg就是S的一个子序列，abcfg就不是S的子序列；
• 子串：子串是一种特殊的子序列，它要求tj - ti = sj - si，即子串的字符要在S中连续。还是设S为adbfhgs，那么adbf是S的一个子串，abfg就不是。
• 后缀：S[0..n]，那么S[i..n] (i>=0)都是S的后缀；
• 公共子序列/串：如果R既是S的子序列/串，又是T 的子序列/串，那么R就是S和T 的公共子序列/串。

最长公共子序列

问题描述

有两个字符串S[0...m]和T[0...n]，求S和T的所有最长公共子序列的长度。

例子

设S=adbfhgs，T=hadeubgs，那么S和T的最长公共子序列为R=adbgs，长度为5。

分析

首先考虑暴力求解。枚举S的所有子序列，总共有2^{m个；然后再枚举T的所有子序列，总共有2}n个；最后一一匹配，总的时间复杂度为O(2^(m+n))。显然是不可行的。

考虑一种动态规划的方法。

• 状态表####

dp[i][j]，i和j分别是S和T的下标，dp[i][j]为当前状态下的最长公共子序列的长度。其中i和j分别从0开始递增，即状态表是从左往右，从上往下依次被填满的（假设左上方的i和j都是0）。

• 基础状态####

dp[0][j]=0，dp[i][0]=0。显然当一个字符串为空时，两字符串的最长公共子序列就是空字符串，长度为0

• 状态转移方程####

dp[i][j]=dp[i-1][j-1]+1, S[i]=T[j];
dp[i][j]=max(dp[i-1][j],dp[i][j-1]), S[i]!=T[j].
当S[i]=T[j]时，如果i-1和j-1状态下的最长公共子序列为R，那么i和j状态下的最长公共子序列就为R+S[i] (T[j])，所以长度会加1；
当S[i]!=T[j]，i和j状态下的最长公共子序列要么是i-1和j状态下的最长公共子序列，要么是i和j-1状态下的最长公共子序列，所以长度取这两个最长公共子序列的长度的最大值。

打印

到目前为止，我们已经得到了一张填好的状态表。那么怎么通过这张状态表打印出对应的最长公共子序列呢？

回溯打印最长公共子序列

从状态表的右下方开始，向上回溯。具体算法详见代码。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;

    int slen = s.length();
    int tlen = t.length();

    vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));

    for (int i = 1; i <= slen; i++)
        for (int j = 1; j <= tlen; j++)
            if (s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    int lcslen = dp[slen][tlen]; // 最长公共子序列长度

    string lcs; // 最长公共子序列
    lcs.resize(lcslen);
    
    // 从右下向左上遍历状态表
    int i = slen, j = tlen, k = lcslen;
    while (i > 0 && j > 0)
    {
        if (s[i - 1] == t[j - 1])
        {
            lcs[--k] = s[i - 1];
            i--; j--;
        }
        else if (dp[i - 1][j] < dp[i][j - 1])
            j--;
        else
            i--;
    }

    cout << "longest common subsequence length: " << lcslen << endl;
    cout << "longest common subsequence: " << lcs << endl;

    return 0;
}

最长公共子串

问题描述

有两个字符串S[0...m]和T[0...n]，求S和T的所有最长公共子串的长度。

例子

设S=adbfhgs，T=hadeubgs，那么S和T的最长公共子串为R=ad或者gs，长度为2。

分析

首先考虑暴力求解。枚举S的所有子串，总共有(m^{2+m)/2个；然后再枚举T的所有子序列，总共有(n}2+n)/2个；最后一一匹配，总的时间复杂度为O(m^2*n2)，也是不可行的。可以使用KMP算法把匹配的复杂度降到O(n)，但是总的复杂度O(m^2*n)还是太高。

考虑一种动态规划的方法。

• 状态表####

dp[i][j]，i和j分别是S和T的下标。注意，这里的dp[i][j]并不是当前状态下的最长公共子串的长度，而是最长公共后缀的长度。举个例子，S为abxcdef，T为frcdef，当i=4，j=3，即i指向d，j指向也是d，则当前字符串abxcd和frcd的最长公共后缀为cd。要明确后缀就是从后往前看，依次进行匹配就行了。其中i和j分别从0开始递增，即状态表是从左往右，从上往下依次被填满的（假设左上方的i和j都是0）。

• 基础状态####

dp[0][j]=0，dp[i][0]=0。显然当一个字符串为空时，两字符串的最长公共子串就是空字符串，长度为0

• 状态转移方程####

dp[i][j]=dp[i-1][j-1]+1, S[i]=T[j];
dp[i][j]=0, S[i]!=T[j];
lcslen=max(lcslen, dp[i][j]).
当S[i]=T[j]时，如果i-1和j-1状态下的最长公共后缀为R，那么i和j状态下的最长公共后缀就为R+S[i] (T[j])，所以长度会加1；设S为abxcdef，T为frcdef，i=4(指向d)，j=3(指向d)，i-1和j-1状态下的最长公共后缀为c，i和j状态下的最长公共后缀就是cd，长度为2；
当S[i]!=T[j]，设S为abxcdef，T为frcdef，i=4(指向d)，j=4(指向e)，则当前字符串abxcd和frcde的最长公共后缀为空，长度为0。
lcslen是最长公共子串的长度，每次更新状态的时候更新。

打印

构建状态表的时候，保存每次检测到的最长公共子串的尾下标，最后从尾下标开始往前查找字符串，直到找到两个不相同的字符为止。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;

    int slen = s.length();
    int tlen = t.length();

    vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));

    int lcsi, lcsj; // 最长公共子串的尾下标
    int lcslen = 0; // 最长公共子串长度
    for (int i = 1; i <= slen; i++)
        for (int j = 1; j <= tlen; j++)
            if (s[i - 1] == t[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > lcslen)
                {
                    lcslen = dp[i][j];
                    lcsi = i;
                    lcsj = j;
                }
            }
                
    string lcs;// 最长公共子串
    lcs.resize(lcslen);

    for (int i = lcsi - 1, j = lcsj - 1, k = lcslen; 
        i >= 0 && j >= 0; )
    {
        if (s[i] == t[j])
        {
            lcs[--k] = s[i];
            i--; j--;
        }
        else
            break;
    }

    cout << "longest common substring length: " << lcslen << endl;
    cout << "longest common substring: " << lcs << endl;

    return 0;
}