作为机试苦手，最近迫不得已准备算法机试，因此有了若干文章 。子串和子序列是一组很容易混淆的概念。两者名称相近，处理方式却差别很大：子串强调连续，常与滑动窗口、前缀和等方法联系在一起；子序列允许跳过元素，往往需要动态规划或贪心与二分。下面做一些介绍。

第一章 基本概念

子串是原字符串或原序列中的一段连续区间。以序列 $(a,b,c,d,e)$ 为例，$(a,b,c)$、$(b,c,d)$ 和 $(d,e)$ 都是子串，$(a,c,e)$ 则不是，因为元素之间发生了跳跃。字符串中的子串通常称为 substring，数组中的连续子数组称为 subarray。长度为 $n$ 的序列共有

$$\frac{n(n+1)}{2}$$

个非空连续子串。

子序列由原序列删除若干元素后得到，它可以不连续，但必须保持原有的相对顺序。同样以 $(a,b,c,d,e)$ 为例，$(a,c,e)$、$(a,b,d)$ 和 $(b,d,e)$ 都是子序列，$(e,c,a)$ 却不是，因为顺序已经改变。判断题型时最重要的区别是：子串强调连续区间，子序列强调相对顺序。

第二章 单个输入中的子串问题

单个输入中的子串问题，本质是在一个字符串或数组中寻找满足条件的连续区间。常用方法包括滑动窗口、前缀和、连续型动态规划、中心扩展，以及在更复杂约束下使用单调队列、单调栈或专门的字符串算法。

2.1 最长无重复字符子串

给定字符串 $\texttt{abcabcbb}$，最长无重复字符子串可以是 $\texttt{abc}$，长度为 $3$。这类问题适合使用滑动窗口：维护连续区间 $[\mathrm{left},\mathrm{right}]$，让区间内始终不存在重复字符；右端点不断向右扩展，新字符导致窗口不合法时，就移动左端点，直到窗口重新合法。每次窗口合法后，用 $right-left+1$ 更新答案。

int left = 0;
int answer = 0;

for (int right = 0; right < n; right++) {
    // 将 a[right] 加入窗口

    while (窗口不合法) {
        // 将 a[left] 移出窗口
        left++;
    }

    answer = max(answer, right - left + 1);
}

滑动窗口也适用于“至多包含 $k$ 种字符”“最多修改 $k$ 个元素”“和不小于目标值的最短正数子数组”等连续区间问题。它们的共同条件是：窗口失效后，可以通过单向移动左端点恢复合法性。左右指针都只向右移动，每个元素最多进入和离开窗口一次，因此时间复杂度为 $O(n)$。

2.2 固定长度子串

若题目要求统计所有长度为 $k$ 的连续区间，例如长度为 $k$ 的子数组最大和、窗口内元音字母的最大数量或每个窗口的字符串哈希值，可以维护一个固定大小的窗口。右端加入新元素后，移出距离它 $k$ 个位置的旧元素；若维护区间和，更新式为

$$sum_{new}=sum_{old}+a[right]-a[right-k]。$$

这样只需常数时间便能从一个窗口过渡到下一个窗口，总时间复杂度为 $O(n)$。

2.3 前缀和与连续区间

多次查询数组区间和时，可以定义前缀和

$$prefix[i]=a_1+a_2+\cdots+a_i，$$

于是区间 $[l,r]$ 的和为

$$sum(l,r)=prefix[r]-prefix[l-1]。$$

前缀和可以把单次区间求和从线性时间降到常数时间，也常与哈希表结合，统计和为指定值的子数组数量。它还可以推广到区间平均值和二维矩阵的子矩形和，但前缀和本身只是快速取得区间信息，是否能满足其他约束仍要结合题目分析。

2.4 最大连续子数组和

以数组 $(-2,1,-3,4,-1,2,1,-5,4)$ 为例，最大连续子数组是 $(4,-1,2,1)$，和为 $6$。设 $dp[i]$ 表示以第 $i$ 个元素结尾的最大连续子数组和，那么当前位置只有两种选择：从 $a[i]$ 重新开始，或者把它接在前一个连续子数组之后，因此

$$dp[i]=\max\left(a[i],dp[i-1]+a[i]\right)，$$

最终答案是 $\max_{1\le i\le n}dp[i]$。由于当前状态只依赖前一个位置，可以将空间压缩为两个变量。

long long current = a[0];
long long answer = a[0];

for (int i = 1; i < n; i++) {
    current = max(
        static_cast<long long>(a[i]),
        current + a[i]
    );

    answer = max(answer, current);
}

这一算法的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

2.5 最长回文子串

回文串关于中心对称，因此最长回文子串可以通过中心扩展求解。回文中心可能是一个字符，如 $\texttt{aba}$；也可能位于两个字符之间，如 $\texttt{abba}$。枚举约 $2n-1$ 个中心，只要 left >= 0​、right < n​ 且 s[left] == s[right]，就继续向两侧扩展。

中心扩展的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。当数据规模较大时，可以改用 Manacher 算法，将时间复杂度降到 $O(n)$。

第三章 多个输入中的公共子串问题

多个输入中的子串问题要求某个连续片段同时出现在两个或多个输入中，最典型的模型是最长公共子串。

3.1 最长公共子串

给定 $s_1=\texttt{ababc}$ 和 $s_2=\texttt{babca}$，最长公共子串为 $\texttt{babc}$，长度为 $4$。定义 $dp[i][j]$ 表示以 $s_1[i-1]$ 和 $s_2[j-1]$ 结尾的最长公共子串长度。这里的“以当前两个字符结尾”十分关键：字符相等时，当前匹配可以接在此前的公共子串后；字符不等时，连续性已经中断，状态必须归零。

$$dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & s1[i-1]=s2[j-1],\\ 0, & s1[i-1]\ne s2[j-1]。 \end{cases}$$

例如 $\texttt{abcXdef}$ 与 $\texttt{abcYdef}$ 分别含有公共子串 $\texttt{abc}$ 和 $\texttt{def}$，但 $\texttt{abcdef}$ 并不是公共子串，所以比较到 $X$ 与 $Y$ 时必须重新计数。实现时只需要保存上一行状态，并记录最佳长度及其在 $s_1$ 中的结束位置。

vector<int> previous(m + 1, 0);
vector<int> current(m + 1, 0);

int bestLength = 0;
int endPosition = 0;

for (int i = 1; i <= n; i++) {
    fill(current.begin(), current.end(), 0);

    for (int j = 1; j <= m; j++) {
        if (s1[i - 1] == s2[j - 1]) {
            current[j] = previous[j - 1] + 1;

            if (current[j] > bestLength) {
                bestLength = current[j];
                endPosition = i;
            }
        }
    }

    swap(previous, current);
}

最长公共子串在 $s_1$ 中的起点为 $\mathrm{endPosition}-\mathrm{bestLength}$，可以通过 s1.substr(endPosition - bestLength, bestLength) 恢复。设两个字符串长度分别为 $n$ 和 $m$，时间复杂度为 $O(nm)$，滚动数组的空间复杂度为 $O(m)$。

3.2 带限制的最长公共子串

公共子串有时还要满足额外限制，例如不能包含数字、只能包含字母、不能出现某些字符，或所有字符必须属于指定集合。处理时只需把合法性判断加入原有转移：两个字符相等且合法时延长，否则归零。

$$dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & s1[i-1]=s2[j-1]\text{ 且字符合法},\\ 0, & \text{其他情况}。 \end{cases}$$

3.3 子串匹配

判断模式串 pattern 是否连续出现在文本串 text 中，规模较小时可以直接使用字符串查找；规模较大或要求所有匹配位置时，可以选择 KMP、Z 函数或字符串哈希。KMP 利用模式串自身的前后缀信息避免文本指针回退，时间复杂度为 $O(n+m)$。

第四章 单个输入中的子序列问题

子序列允许跳过元素，但不能改变相对顺序。单个输入中常见的问题包括最长递增子序列、最长回文子序列、判断一个序列是否为另一个序列的子序列，以及其他删除或选择型动态规划问题。

4.1 最长递增子序列的动态规划方法

给定序列 $(10,9,2,5,3,7,101,18)$，一个最长严格递增子序列是 $(2,3,7,18)$，长度为 $4$，这些元素不必连续。定义 $dp[i]$ 表示以 $a[i]$ 结尾的最长严格递增子序列长度，每个元素本身可构成长度为 $1$ 的子序列，所以初始值为 $dp[i]=1$。枚举 $i$ 之前的所有位置 $j$，若 $a[j]<a[i]$，就可以把 $a[i]$ 接到原子序列末尾：

$$dp[i]=\max\left(dp[i],dp[j]+1\right)。$$

最终答案为 $\max_{1\le i\le n}dp[i]$。这一写法需要枚举所有二元位置对，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$，适合规模较小的情况。

4.2 最长递增子序列的贪心与二分方法

当数据规模达到 $10^5$ 或 $10^6$ 时，需要把复杂度优化到 $O(n\log n)$。维护递增数组 tails​，其中 tails[k] 表示长度为 $k+1$ 的严格递增子序列所能取得的最小结尾值。tails 不一定是原序列中一条真实的最长递增子序列，但它的长度一定等于答案。保留最小结尾是因为，在长度相同的情况下，以 $6$ 结尾的序列比以 $9$ 结尾的序列更容易接入后续元素。

处理当前元素 $x$ 时，①在 tails 中找到第一个大于等于 $x$ 的位置；②若该位置存在，就用 $x$ 替换原值；③若不存在，就把 $x$ 添加到末尾。

vector<int> tails;

for (int x : a) {
    auto it = lower_bound(
        tails.begin(),
        tails.end(),
        x
    );

    if (it == tails.end()) {
        tails.push_back(x);
    } else {
        *it = x;
    }
}

严格递增使用 ​lower_bound​​，因为相等元素只能替换，不能增加 tails 的长度。例如处理 $(1,2,2,3)$ 时，tails 依次为 $1$、$(1,2)$、$(1,2)$、$(1,2,3)$，答案为 $3$。若题目要求非递减子序列，则应使用 upper_bound，让相等元素可以接到已有序列之后。

4.3 最长回文子序列

给定字符串 $\texttt{bbbab}$，最长回文子序列是 $\texttt{bbbb}$，长度为 $4$。它不要求连续，因此与最长回文子串不同。定义 $dp[l][r]$ 表示区间 $s[l\ldots r]$ 中最长回文子序列的长度。若两端字符相等，可以把两端同时加入答案；若不相等，则至少舍弃其中一端。

$$dp[l][r]= \begin{cases} dp[l+1][r-1]+2, & s[l]=s[r],\\ \max\left(dp[l+1][r],dp[l][r-1]\right), & s[l]\ne s[r]。 \end{cases}$$

单个字符本身就是长度为 $1$ 的回文子序列，因此初始化为 $dp[i][i]=1$。时间复杂度和空间复杂度都是 $O(n^2)$。

4.4 判断子序列

判断序列 $A$ 是否为序列 $B$ 的子序列，可以使用双指针。让 $i$ 指向 $A$，用 $j$ 从左到右扫描 $B$；当 A[i] == B[j] 时令 $i$ 后移。扫描结束后，若 $i=|A|$，说明 $A$ 中的全部元素都已按顺序匹配。整个过程只扫描一次 $B$，时间复杂度为 $O(|B|)$。

第五章 多个输入中的公共子序列问题

公共子序列要求选出的元素在每个输入中都保持相对顺序，但不要求连续。最典型的模型是最长公共子序列。

5.1 最长公共子序列

给定 $s_1=\texttt{abcde}$ 和 $s_2=\texttt{ace}$，最长公共子序列为 $\texttt{ace}$，长度为 $3$。定义 $dp[i][j]$ 表示第一个序列前 $i$ 个元素与第二个序列前 $j$ 个元素的最长公共子序列长度。当前元素相等时，可以把它加入公共子序列；当前元素不同时，不能同时使用这两个元素，需要选择舍弃一侧后较优的状态。

$$dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & s1[i-1]=s2[j-1],\\ \max\left(dp[i-1][j],dp[i][j-1]\right), & s1[i-1]\ne s2[j-1]。 \end{cases}$$

vector<vector<int>> dp(
    n + 1,
    vector<int>(m + 1, 0)
);

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (s1[i - 1] == s2[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
            dp[i][j] = max(
                dp[i - 1][j],
                dp[i][j - 1]
            );
        }
    }
}

设两个序列长度分别为 $n$ 和 $m$，时间和空间复杂度均为 $O(nm)$。如果只求长度，可以使用滚动数组，把空间复杂度降为 $O(\min(n,m))$；如果还要输出具体序列，则通常需要保留完整状态或可供回溯的信息。

5.2 恢复具体的最长公共子序列

从 $dp[n][m]$ 开始回溯：①当前两个元素相等时，把该元素加入答案并向左上移动；②不相等时，移动到数值较大的相邻状态；③回溯得到的次序与原序列相反，最后再翻转。只保存滚动数组通常无法直接恢复具体序列，因为此前的状态已经被覆盖。

5.3 公共子串与公共子序列的区别

最长公共子串在字符不同时令 $dp[i][j]=0$，因为连续性已经破坏；最长公共子序列则令 $dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$，因为它可以跳过其中一个字符。简而言之，公共子串不等就中断，公共子序列不等就跳过。

5.4 特殊 LCS：一个序列中的元素互不重复

若第一个序列中的元素互不重复、第二个序列允许重复，且 $n$ 可能达到 $10^6$，普通 $O(n^2)$ 的 LCS 无法使用。此时可以记录第一个序列中每个元素的位置，再把第二个序列中的元素替换为对应的位置；不存在于第一个序列中的元素直接忽略。

例如第一个序列为 $(3,1,5,2,4)$，位置映射如下：

第二个序列 $(1,3,2,5,2)$ 映射后得到 $(2,1,4,3,4)$。从第二个序列中选出的元素已经满足它自身的先后顺序；若还要构成第一个序列的子序列，对应位置就必须严格递增，因此原问题转化为映射后位置序列的 LIS。

第二个序列中的重复元素不会破坏这一转化。例如 $A=(1,2,3)$、$B=(1,1,1)$ 映射后为 $(1,1,1)$，严格递增子序列最多选择一个 $1$，正好对应第一个序列中只有一个 $1$。所以这里必须使用 lower_bound 求严格递增子序列。建立位置映射需要 $O(n)$，求 LIS 需要 $O(n\log n)$，总复杂度为 $O(n\log n)$。

第六章 算法选择

第七章 根据数据范围选择复杂度

数据范围直接限制了可用算法。下表只给出常见经验，实际还要考虑常数、内存限制和测试组数。

对于两个长度均为 $n$ 的序列，普通 LCS 的状态数为 $O(n^2)$。当 $n=10^6$ 时，状态数量达到 $10^{12}$，显然无法计算，此时必须利用互不重复、值域较小或其他题目条件进行转化。

第八章 常见错误

这类问题中最容易出现的错误可以归为六类。①把子串当成子序列，在最长公共子串失配时仍使用 $\max(dp[i-1][j],dp[i][j-1])$，从而错误地允许跳过字符；②最长公共子串失配后没有归零，把两个不连续的公共片段拼在一起；③混淆严格递增与非递减，前者应使用 lower_bound​，后者应使用 upper_bound。

另外，④tails 保存的是每种长度所能取得的最小结尾值，并不一定是一条真实的最长递增子序列；⑤若连续匹配一直延伸到循环末尾，只在失配时更新答案会漏掉最终结果，因此每次成功更新状态后都应同步更新全局最优值；⑥如果题目要求输出具体方案，仅保存长度往往不够，还要根据算法记录结束位置、前驱位置、状态转移方向或完整动态规划表。

第九章 核心结论

子串问题围绕连续区间展开，常用滑动窗口、前缀和、连续型动态规划、中心扩展和字符串匹配；子序列允许跳过元素，常用选择型动态规划、LIS、LCS、区间动态规划与双指针。做题时先判断“是否必须连续”，再根据输入数量、数据范围和是否需要恢复具体方案选择算法。

最长公共子串与最长公共子序列的核心转移分别为：

$$dp_{substring}[i][j]= \begin{cases} dp[i-1][j-1]+1, & a[i-1]=b[j-1],\\ 0, & a[i-1]\ne b[j-1], \end{cases}$$

$$dp_{subsequence}[i][j]= \begin{cases} dp[i-1][j-1]+1, & a[i-1]=b[j-1],\\ \max\left(dp[i-1][j],dp[i][j-1]\right), & a[i-1]\ne b[j-1]。 \end{cases}$$

最后记住三点即可：==子串必须连续，子序列只保持顺序；公共子串不等就中断，公共子序列不等就跳过。== 严格递增使用 lower_bound​，非递减使用 upper_bound。