什么是「公共子序列」

上一节的子序列是从一串里挑数、保持原次序。这一节有两串，要找一条同时是它们各自子序列的序列——它就是一条公共子序列；其中最长的那条，长度就是 LCS （Longest Common Subsequence）。注意是「子序列」不是「子串」：字符不必相邻，只要在两串里都能按原次序依次找到。

拿一个小例子： $A=\texttt{ABCBDAB}$ 、 $B=\texttt{BDCAB}$ 。 $\texttt{BD}$ 在两串里都出现且次序一致，是公共子序列（长 2）； $\texttt{BCAB}$ 也是——它在 A 里是第 2、3、6、7 位，在 B 里是第 1、3、4、5 位，两边都递增。能不能更长？试遍所有挑法，最长就是 4。

A=ABCBDAB、B=BDCAB。连线把公共子序列 B C A B 的四对字符勾出——线不交叉，正说明它在两串里的下标各自递增（保持了原次序）。

为什么不能贪心地「从头扫，遇到相同字符就配一对」？看 $A=\texttt{AB}$ 、 $B=\texttt{BA}$ ：贪心先把两个 $\texttt{A}$ 配上，之后 $\texttt{B}$ 在 A 里已经没了往后的位置——只得长度 1；可正解是先放 $\texttt{B}$ 再放 $\texttt{A}$ ，同样长度 1，这里恰好不亏，但把串拉长就会出岔：此刻配哪一对最好，取决于后面还能配出多少——又是需要 DP 的信号。

穷举呢？A 的子序列有 $2^{|A|}$ 条，逐条去 B 里验证，指数级，串一长就无从枚举。下面用一张二维表把它压成 $O(|A|\cdot|B|)$ 。

状态与转移：只看两串的「末位」

两串一起处理，抓手是各自的前缀。设 $dp[i][j]$ 表示：A 的前 $i$ 个字符与 B 的前 $j$ 个字符的最长公共子序列长度。要算它，只需盯住两串当前的最后一个字符 $A_i$ 与 $B_j$ ——它俩相不相等，决定了两条截然不同的路。

算 dp[i][j] 只看末位：相等就把这对配上、各退一格，长度 = 左上 + 1；不等则末位至少有一个用不上，丢 A 末位或丢 B 末位，取较大者。

末位相等（ $A_i=B_j$ ）：这对字符可以且值得配成公共子序列的最后一对。把它配上后，剩下的问题变成「A 前 $i-1$ 与 B 前 $j-1$ 的 LCS」，长度在它基础上 $+1$ ：

dp[i][j]=dp[i-1][j-1]+1

末位不等（ $A_i\ne B_j$ ）：这两个末位配不成同一对，那么最优解里 $A_i$ 与 $B_j$ 至少有一个不会被用到。于是要么丢掉 $A_i$ （转成 $dp[i-1][j]$ ），要么丢掉 $B_j$ （转成 $dp[i][j-1]$ ），谁大取谁：

dp[i][j]=\max\big(dp[i-1][j],\ dp[i][j-1]\big)

边界： $dp[0][j]=dp[i][0]=0$ （任一串为空，公共子序列长度为 0）。答案： $dp[|A|][|B|]$ 。

本质

两串的 LCS 被「各自前缀 + 只看末位」拆成了一张 $(|A|{+}1)\times(|B|{+}1)$ 的表：每格只依赖左上、上、左三个已算好的邻居，一步 $O(1)$ 。于是 $2^{|A|}$ 的枚举被 $O(|A|\cdot|B|)$ 个格子装下。相等走对角、不等走上/左——这条「对角 vs 直行」的分野是全表的灵魂。

跟着算一遍

用一对更短的串 $A=\texttt{ABCB}$ 、 $B=\texttt{BDCB}$ 走几格（下标从 1 记），把两条规则跑起来：

0

第 0 行 / 第 0 列。 任一串取空前缀，公共子序列只能是空的：

dp[0][\cdot]=dp[\cdot][0]=0

。整张表的地基。

1

末位相等的格。 看

dp[1][1]

：

A_1=\texttt{A}

、

B_1=\texttt{B}

不等 → 取

\max(dp[0][1],dp[1][0])=0

。再看

dp[2][1]

：

A_2=\texttt{B}=B_1

相等 →

dp[1][0]+1=1

。第一对

\texttt{B}

配上了。

2

末位不等的格。 看

dp[3][3]

：

A_3=\texttt{C}=B_3

相等 → 左上

dp[2][2]+1

。而如

dp[3][2]

：

A_3=\texttt{C}\ne B_2=\texttt{D}

→ 取上、左较大者，长度不涨。

3

读答案。 填到右下角

dp[4][4]=3

——

A=\texttt{ABCB}

与

B=\texttt{BDCB}

的 LCS 长度是 3，正是

\texttt{BCB}

。

下面的演示把整张

dp

表逐格填满，高亮每格来自左上（相等）还是上/左（不等）；填完再回溯出一条 LCS。改两串的字符、加删长度，看它实时重算。

看它一格一格长出来，再回溯出答案

当前两串的最长公共子序列：长度 4（一条 LCS = BCAB）——绿色斜格是回溯时摘下字符的地方。

∅

B

D

C

A

B

∅

A

B

C

B

D

A

B

0

·

0

·

0

·

0

·

0

·

0

·

0

·

当前计算依赖来源被选转移已确定

dp[i][0]=dp[0][j]=0

第 0 行、第 0 列是空串地基：任何字符串与空串的公共子序列长度都是 0。

进度

已暂停，第 1 步，共 37 步，1 倍速

不止长度：回溯重构一条 LCS

$dp[|A|][|B|]$ 只给出长度。想要那条子序列本身，就从右下角沿转移的来路往回走：在格 $(i,j)$ ，若当初是「相等」填的（ $A_i=B_j$ ），就斜着走到 $(i-1,j-1)$ ，并摘下这个字符；否则朝当初更大的那个来源（上或左）走一格、不摘字符。走到边界为止，把摘到的字符逆序拼起来，就是一条 LCS。

从右下角回溯：绿格是「相等」时斜向的一步，各摘下一个字符；灰路是「不等」时的直行（不摘）。逆序拼出 B C B——正是这对串的一条 LCS。

要留意 LCS 可能不唯一：当上、左来源一样大时，往哪边走都合法，会回溯出不同但等长的 LCS。想统计「到底有多少条」，就得给方案数也开一张表——这正是本页例题 P2516 要处理的（相等时方案继承左上，不等时把达标来源并起来、再用容斥减去重复计入的左上）。

深化：当两串是「排列」——降到 O(n log n)

标准 LCS 是 $O(|A|\cdot|B|)$ 。当 $|A|=|B|=n$ 都到 $10^5$ ， $n^2=10^{10}$ 必然超时。但有一类特殊情形能大幅提速：两串是同一集合的两个排列（各值恰好出现一次，如都是 $1\dots n$ 的重排）。此时有一个漂亮的转化——LCS 可以变成 LIS。

关键观察：既然 A 是排列，每个值在 A 里有唯一的位置。把 B 里的每个值，都替换成「它在 A 中的位置」，得到一串位置序列。那么——

A 取 1 2 3 4 5（位置即数值），B=2 4 1 5 3 逐个换成它在 A 里的位置，得位置序列 2 4 1 5 3；它的一条最长上升子序列 2 4 5（长 3）就等于 LCS 长度。

为什么位置序列的 LIS 就是 LCS？ 一条公共子序列，等价于在 A 里选一批位置、在 B 里选同样一批值，且两边次序一致。映射后，B 中被选值的相对次序就是它们出现的先后（沿 B 从左到右，即位置序列的下标递增）；而「它们在 A 里也保持同样次序」翻译过来，正是这些位置数值递增——两个「递增」合起来，恰是位置序列的一条上升子序列。于是最长公共子序列 = 位置序列的最长上升子序列。

而 LIS 有 $O(n\log n)$ 的贪心 + 二分解法（维护 $tails$ 、 $\texttt{lower\_bound}$ 替换）。绕这一圈，排列 LCS 就从 $O(n^2)$ 降到了 $O(n\log n)$ 。

下面的转化器把这套映射逐步演示：逐个把 B 的值换成它在 A 里的位置，映完再点亮位置序列里的一条 LIS——它的长度就是 LCS。换第二个预设（A 乱序）看一般映射。

映射规则：把 A 里每个值记下它的位置（第几个）A = [1, 2, 3, 4, 5]

1

2

3

4

5

上排＝值，下排＝它在 A 中的位置（1-based）。第一组 A 已排序，值恰好等于位置。

串 B 的原始值已映射 0/5

1

2

4

3

1

4

5

3

换成位置后的位置序列——对它求最长上升子序列…

1

·

2

·

3

·

4

·

5

·

点播放或 下一步 开始：逐个把 B 的值换成它在 A 里的位置，得到一串位置序列；这串序列的 LIS 长度就等于 LCS(A, B) 长度。

进度

已暂停，第 1 步，共 7 步，1 倍速

边界 · 只对「排列 / 无重复」直接成立

「LCS→LIS」的降维前提是「一串里每个值唯一」（映射才是单值函数）。若值有界重复（如每种恰好出现 $k$ 次），需把一个值展开成它的多个位置、且按位置降序铺开再求 LIS——见例题 P4303。若是普通带重复的两串，则老老实实用 $O(|A|\cdot|B|)$ 的二维 DP，别硬套。另有一类叫 LCIS（最长公共上升子序列），要求公共子序列同时严格上升——它是「LCS 的匹配 + LIS 的上升」两个约束的复合，需设二维状态 $f[i][j]$ 「用到 $a_i$ 、且以 $b_j$ 结尾」并配合前缀最优优化到 $O(nm)$ ；洛谷原生 P/B 题库暂无纯 LCIS 模板，此处只作为概念点点到，不强凑题号。

例题

P1439【模板】最长公共子序列洛谷原生提高+/省选-

题意

给定

1\dots n

的两个排列，求它们的最长公共子序列长度，

n\le 10^5

。

为什么选它

排列 LCS→LIS 的招牌模板题：

n=10^5

卡死

O(n^2)

，逼你把「两串是排列」这个条件用足——映射位置、转成 LIS、二分求解。把本节深化那套转化一次写通的最佳载体。

转移 · 复杂度

记

p[a_i]=i

，令

b_i\gets p[b_i]

；对

b[]

求 LIS（

\texttt{lower\_bound}

二分）。时间

O(n\log n)

。

参考代码（映射位置 + LIS 二分）

C++

在洛谷打开 P1439

#include <algorithm>
#include <iostream>
using namespace std;
#define MX 100005

int n, len;
int a[MX], p[MX];   // p[值] = 该值在 a 中的位置
int b[MX], g[MX];   // g[k] = 长度 k 的上升子序列的最小结尾（单调递增）

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        p[a[i]] = i;                // 记下 a 中每个值的位置
    }
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        b[i] = p[x];                // ★把 b 的值换成它在 a 中的位置
    }

    // 排列 LCS = 位置序列 b[] 的 LIS，二分 O(n log n)
    for (int i = 1; i <= n; i++)
    {
        if (len == 0 || b[i] > g[len])
        {
            g[++len] = b[i];        // 比末尾大，接到最长后面
        }
        else
        {
            int l = 1, r = len;
            while (l <= r)          // lower_bound：第一个 >= b[i] 的位置
            {
                int mid = (l + r) >> 1;
                g[mid] >= b[i] ? r = mid - 1 : l = mid + 1;
            }
            g[l] = b[i];
        }
    }

    cout << len << endl;
    return 0;
}
// TAG: 线性DP LCS 排列 LIS 二分 O(nlogn)

P4303[AHOI2006] 基因匹配AHOI2006提高+/省选-

题意

两串基因序列，每串长

5n

，且

1\dots n

每种基因在每串里恰好出现 5 次。求两串的最长公共子序列长度。

为什么选它

排列 LCS→LIS 的「有界重复」变体：值不再唯一（各出现 5 次），直接映射会一对多。技巧是把每个值展开成它在 A 中的 5 个位置、按降序铺开——降序保证同一值的多个位置在 LIS 里至多选中一个，恰好等价于 LCS 的匹配约束。展开后序列长

5n

，再跑 LIS。它教会你「重复值」如何归约回 LIS。

转移 · 复杂度

对 A 建位置表

pos[v]

（值

v

的升序位置）；扫 B，把每个值的位置降序压入序列，再求其 LIS。时间

O(5n\log(5n))

。

参考代码（位置展开 + LIS 二分）

C++

在洛谷打开 P4303

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define MX 100005

int n, len;
vector<int> pos[MX];   // pos[值] = 该值在 a 中出现的所有位置（升序）
int b[5 * MX], g[5 * MX];

int main()
{
    cin >> n;
    int tot = 5 * n;                    // 每种基因恰好出现 5 次
    for (int i = 1; i <= tot; i++)
    {
        int x;
        cin >> x;
        pos[x].push_back(i);            // a 中位置，天然升序
    }

    int cnt = 0;
    for (int i = 1; i <= tot; i++)
    {
        int x;
        cin >> x;
        // ★把 b 里的 x 展开成它在 a 中的位置，且按【降序】铺开，
        // 这样同一个值的 5 个位置在 LIS 里最多被选中一个，等价 LCS 的匹配约束。
        for (int k = (int)pos[x].size() - 1; k >= 0; k--)
        {
            b[++cnt] = pos[x][k];
        }
    }

    // 对展开后的位置序列求 LIS（严格上升），二分 O(N log N)，N = 5n
    for (int i = 1; i <= cnt; i++)
    {
        if (len == 0 || b[i] > g[len])
        {
            g[++len] = b[i];
        }
        else
        {
            int l = 1, r = len;
            while (l <= r)              // 第一个 >= b[i] 的位置
            {
                int mid = (l + r) >> 1;
                g[mid] >= b[i] ? r = mid - 1 : l = mid + 1;
            }
            g[l] = b[i];
        }
    }

    cout << len << endl;
    return 0;
}
// TAG: 线性DP LCS 有界重复 展开 LIS 二分

P2516[HAOI2010] 最长公共子序列洛谷原生提高+/省选-

题意

给定两串（末尾各带一个多余字符），求它们的 LCS 长度，以及不同 LCS 的方案数（对

10^8

取模）。

为什么选它

回到标准二维 LCS，但在长度之外再叠一层计数 DP：既要

f[i][j]

记长度，又要

c[i][j]

记「取得该长度的方案数」。难点是不等时把上、左两个达标来源并起来会重复计入左上，须容斥减一次。是把 LCS 从「求长度」推向「数方案」的经典一题。

转移 · 复杂度

相等：

f{+}1

、

c\gets c_{\nwarrow}

；不等：

f=\max

，

c

并入长度达标的上/左，再减去左上（若也达标）。时间

O(|A|\cdot|B|)

。

参考代码（长度 + 方案数容斥）

C++

在洛谷打开 P2516

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
#define MX 5005
const int MOD = 100000000;   // 答案对 10^8 取模

char sa[MX], sb[MX];
int la, lb;
int f[MX][MX];               // f[i][j]：LCS 长度
int c[MX][MX];               // c[i][j]：取得该长度的方案数

int main()
{
    cin >> (sa + 1) >> (sb + 1);
    la = strlen(sa + 1) - 1;         // 题目串尾带一个多余字符，去掉
    lb = strlen(sb + 1) - 1;

    for (int i = 0; i <= la; i++)    // 与空串比：长度 0，「什么都不选」算 1 种
    {
        c[i][0] = 1;
    }
    for (int j = 0; j <= lb; j++)
    {
        c[0][j] = 1;
    }

    for (int i = 1; i <= la; i++)
    {
        for (int j = 1; j <= lb; j++)
        {
            if (sa[i] == sb[j])
            {
                f[i][j] = f[i - 1][j - 1] + 1;
                c[i][j] = c[i - 1][j - 1];       // 末位配对，方案继承左上
            }
            else
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (f[i - 1][j] == f[i][j])      // 谁的长度达标就并进来
                {
                    c[i][j] = (c[i][j] + c[i - 1][j]) % MOD;
                }
                if (f[i][j - 1] == f[i][j])
                {
                    c[i][j] = (c[i][j] + c[i][j - 1]) % MOD;
                }
                if (f[i - 1][j - 1] == f[i][j])  // ★容斥：左上被重复计入，减掉
                {
                    c[i][j] = ((c[i][j] - c[i - 1][j - 1]) % MOD + MOD) % MOD;
                }
            }
        }
    }

    cout << f[la][lb] << endl;
    cout << c[la][lb] % MOD << endl;
    return 0;
}
// TAG: 线性DP LCS 计数 容斥

练习

说明：纯 LCIS（最长公共上升子序列）在洛谷原生 P/B 题库暂无对应模板题（仅有 U 前缀的用户自建题）。它的正解是「LCS 匹配 + LIS 上升」的复合二维状态，已在上方深化的「常见陷阱」框里作为概念点讲解，这里不强凑题号。下面两题分别从「子序列思想」与「加权 LCS / 对齐」两侧巩固。

P2837晚餐队列优化 Dining Cows子序列思想：要删掉最少的牛，等价于保留最长的一段「先按体型分组、组内编号递增」的子序列——把它转成一维 LIS/前缀最优来做，答案 = 总数 − 最长保留。在洛谷打开

P1279字串距离加权 LCS / 序列对齐：允许在两串里插入空格对齐，未匹配位置罚 k、错配位置罚字符差，求最小总距离——把 LCS 的「相等/不等」转移换成「对齐/跳过」的带权版二维 DP。（亦属 A5 编辑距离一族。）在洛谷打开

最长公共子序列 LCS

本课摘要

什么是「公共子序列」

状态与转移：只看两串的「末位」

本质

跟着算一遍

看它一格一格长出来，再回溯出答案

不止长度：回溯重构一条 LCS

深化：当两串是「排列」——降到 O(n log n)

边界 · 只对「排列 / 无重复」直接成立

例题

练习