重拾 DP（二）：字符串背景下的 DP

__biu_biu_biu__ · 2026-07-09 21:21:46 · 算法·理论

零、前言

下一期预告：重拾 DP（三）：DP 的数据结构优化。

上一期地址在这里，欢迎大家品鉴。

至于什么时候将树形 DP。这个我还没有想好。

一、KMP 与 DP

一般这类题目通常是关于子串类的，此时 DP 的转移类似于 dp_i=dp_{f(i)}+v(i)，其中 f(i),v(i) 的转移跟字符串的子串有关，且经过分析，该子串可以通过 KMP 的 \pi 数组快速求出，如循环节、失配指针等。

转移需要通过 KMP 辅助求出，具体题目具体分析，因题而异，我们给出很多道例题来举例：

P3082 [USACO13MAR] Necklace G

给你字符串 S 和 T，求最少在 S 中删掉多少个字符才能使得 T 不是 S 的子串。1\le |S|\le 10^4,1\le |T|\le 10^3。

考虑 dp_{i} 表示 S_{1}\sim S_i 都不包含 T 作为子串的最少操作次数，但是这个东西无法转移，因为你不知道删除一个字符后是否使后面的少删或多删，是有后效性的。

由于你的删除是跟 T 有关系的，所以我们不妨添加一维关于 T 的，即 dp_{i,j} 表示 S 中前 i 项未出现 T，且此时的 T 的前 j 位作为现在 S 的后缀时最少删的次数。

如果删这一位，则删完后有 j 项作为后缀，说明前 i-1 项就以 j 项作为后缀了，因此有 dp_{i,j}=dp_{i-1,j}+1。

如果不删，则说明这一位必须要满足 S_i=T_j，且前 i-1 项剩下的必须要以 T_{1}\sim T_{j-1} 结尾，不好操作，考虑将填表法换成刷表法。

对于 dp_{i,j} 这一项，则有 dp_{i+1,j}=dp_{i,j}+1，此时处理了删除；还有 dp_{i+1,f(i+1,j-1)}=dp_{i,j}，其中 f(i+1,j-1) 表示假设前 j-1 项均以匹配，则添加第 i+1 项后与 T 匹配最多能匹配到哪个位置。

现在我们要高效处理这个 f 函数。考虑一种简单的情况：对于 i+1 项与 j 项匹配，即 S_{i+1}=T_j，则有 f(i+1,j-1)=j。

如果 S_{i+1}\not=T_j，根据 KMP 的思想，我们的 \pi 数组可以帮我们贪心地找到次长的匹配，即 f(i+1,j-1)=f(i+1,\pi_{j-1})。

所以我们只需要在 T 上跑一遍 KMP，求出 f 后就可以推出 dp 了，答案为 \min\limits_{0\le k<|T|} dp_{n,k}。

P3426 [POI 2005] SZA-Template

给你字符串 S，求一个印章 T 使得字符串 S 用印章 T 可以被全部覆盖。1\le |S| \le 5\times 10^5。

考虑 dp_i 表示能够覆盖 S_{1\sim i} 的最短长度。我们发现相当于你要覆盖 S_{1\sim i} 相当于你要覆盖 ·S_{1\sim \pi_i}，这样的话你才有可能覆盖 dp_i，所以答案至少为 dp_{\pi_i}。

那么什么时候的答案是 dp_{\pi_i} 呢？显然，如果 S_{1\sim \pi_i} 和 S_{i-\pi_i+1\sim i} 重合了，则一定可以覆盖。

我们推广一下，发现如果有一个 j 在 i-\pi_i\sim i 之间，且 1\sim j 的最短印章和 1\sim \pi_i 是吻合的，又因为 j+1\sim n 在 i-\pi_i+1\sim i 内部，所以使用 j 号点的方案再加上这个循环节就一定可以拼出 1\sim i。

那么怎么判定 1\sim j 和 1\sim \pi_i 的印章是吻合的呢？1\sim j 使用的印章是 [1,dp_{j}]，1\sim \pi_i 使用的印章是 [1,\pi_i]，所以如果两个印章相同一定是 dp_j=\pi_i，所以当 dp_j=\pi_i 且 i-\pi_i\le j<i 时，dp_i 的答案为 dp_{\pi_i}。

否则，你的最长公共前后缀 \pi_i 都不满足了，剩下的肯定也都不满足，答案只能为 i。

P3618 误会

给你一个串 S 和 T，可以将 S 的子串 X 满足 X=T 的将 X 替换为 *，不能同时进行两次替换。求替换后的不同串的方案数。1\le |S|,|T|\le 10^5。

考虑 dp_i 表示替换到 S 的第 i 位时的方案数。

显然，我们有 dp_i=dp_{i-1}，那么如果 S_{i-|T|+1}\sim S_i 可以被替换的话，还有 dp_i=dp_{i-|T|}+1。

Trie 与 DP

Trie 与 DP 会有两种类型，一种是 Trie 优化 DP，一种是 Trie 上 DP。

Trie 优化 DP 的核心思想是避免重新匹配，利用 Trie 快速匹配的特性避免回溯，直接从上一次的开始匹配。当然，如果字典的大小很大，但长度很小，也很使用 Trie 来优化 DP。

Trie 上 DP 是用来处理很困难的前缀关系和转移时，可以转换成 Trie 上 DP，从困难的普通 DP 转为树上 DP。

下面我们聚精到例题上。

P1470 [IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

求 S 的最长前缀 S'，使得 S' 可以由词典 T 中的串组成。1\le |T|\le 200,1\le |T_i|\le 10，1\le |S|\le 5\times 10^5。

考虑 dp_i 表示前缀 S_{1\sim i} 是否可以由 T 组成，则有 dp_i = |_{1\le j<i\land S_{j+1\sim i}\in T} dp_j，由于 T_i 的长度很小，所以考虑 Trie。

我们可以倒着枚举 j，从 i\to 1，这样的话把 T 中的所有串反转后加入 Trie 中，就可以一步一步跳来判断是否为前缀了。

时间复杂度 O(n\max |T_i|)。

P1688 新单词接龙问题

如果一个字符串 S 能修改一个字符，增加一个字符，删除一个字符变成 T，则称 S 和 T 是牛的。求从字符串序列 S_1\sim S_n 中选出尽可能多的数量，使得相邻两个字符串是牛的，切这些字符串按字典序排序。1\le n\le 2.5\times 10^4。

考虑 dp_i 表示以第 i 个字符串结尾的最长的接龙的长度。

则有 dp_i=\max\limits_{1\le j<i\land f(i,j)=1} dp_j+1，其中 dp_j 表示 S_i,S_j 是否可以接龙。

如果直接处理是 O(n^2) 的，考虑优化。

我们先从修改入手：修改的本质是除了 x 位， S_i,S_j 其他位都是相同的，而 Trie 可以高效的转移末尾字符不同的情况，就是所有兄弟节点的转移，因此我们考虑使用 Trie 来解决修改的问题。

我们可以把循环移位 x 次后的字符串放进第 x 棵 Trie 里。这样一来，我们的一次修改操作总会根据循环移位移到末尾去，就可以高效的处理了。这部分的时间复杂度是 O(n\max |S|)。

添加字符相当于可以在原字符串随便放上一个字符，补成同样的长度，然后变成修改操作。注意这里的转移是在每个位置后面都插入字符在判断的，因为你无法判断添加字符是在哪个位置上的，时间复杂度 O(n\max |S|^2)。

对于删除操作，我们可以在其他字符串添加字符，还可以再构建 |S| 棵 Trie，第 i 棵表示在每个字符串的第 i 个字符后面添加一个特殊字符后形成的 Trie，这样的话该字符串可以在这 |S| 棵 Trie 上匹配进行转移，本质上还是修改字符。

好像有点卡空间，时间复杂度 O(n\max |S|^3)，是标程的 4096 倍。

但是好像会被卡空间使用儿子兄弟表示法或链式前向星存儿子即可。

以下是 Trie 上树形 DP 的例题。

P1666 前缀单词

给你 n 个字符串，求有多少个子集使得所选的任意两个字符串没有前缀关系。l\le n\le 50。

考虑建出 Trie，这样前缀关系就相当于选出的子集没有祖先关系。

定义 dp_u 表示以 u 的子树的方案数。

则 u 不选，它的所有儿子都没有祖先关系，dp_u=\prod\limits_{v\in son_u} dp_v。

如果 u 是一个串的结尾，则说明 dp_u 还可以只选它本身，方案数是 1。

P7537 [COCI 2016/2017 #4] Rima

题目描述简洁，此处不再赘述。

首先将字符串反转，后缀转前缀。

我们注意到如果两个字符串是押韵的，则当且仅当两个字符串在 Trie 上呈兄弟或父子关系。

考虑树形 DP，定义 dp_u 表示 u 的子树的答案。

考虑找到儿子中答案最大的两个点 x,y，则转移就是从点 x 跑到点 y，并且在计算路径上的所有答案，即 dp_u=dp_x+dp_y+\sum\limits_{v\in son_u\land v\not=x,y} cnt_i，其中 cnt_i 表示当前这个节点是否作为结尾字符出现。

但是这样的话我们是无法往上转移的，所以再记录可以向上转移的 dp'_u，则 dp_u=dp'_x+dp'_y+\sum\limits_{v\in son_u\land v\not=x,y}cnt_i，向上转移只能选择一个链，但其他儿子是可以选的（前提是 u 点是某一个字符串的结尾，否则整个转移失效），即 dp_u=dp'_x+\sum\limits_{v\in son_u\land v\not=x} cnt_i。

P12238 [蓝桥杯 2023 国 Java A] 单词分类

你有 n 个字符串 S_1,S_2,\dots S_n，选出 K 个前缀，每个字符串有且仅有一个前缀在这 K 个前缀出现过，且这 K 个前缀每个都至少出现一次，求方案数。1\le n\le 200,1\le k\le 100,1\le |S|\le 10。

看到前缀关系，考虑建出 Trie，发现只能选树上的节点，且满足一个点 u 和它的祖先不能同时被选，定义 dp_{u,k} 表示 u 子树选择了 k 个的方案数。

则有 dp_{u,k}=\sum\limits_{v\in son_u}dp_{v,p}\times dp_{u,k-p}。

String MST

给你 n 个字符串 S_1,S_2,\dots S_n，你还有 n 个点，第 i 个点与第 j 个点之间的边权为 S_i 和 S_j 的最长公共子序列的长度，求这 n 个点的最大生成树。

建出 Trie，考虑合并 u 的若干个儿子，发现要使得生成树最大则在 u 的合并是最优秀的，所以合并 u 的 x 个儿子的最大代价即为 (son_u-1)\times dep_u，因此答案即为 \sum (son_u-1)\times dep_u。

AC 自动机上 DP

由于 AC 自动机 nxt 节点的特殊性，它可以转移所有当前节点的所有后缀字符串，可以提供高效的转移。

还有另一种，由于 AC 自动机是一个 DAG，所以它还可以在节点上跑拓扑 DP，比较猎奇，这里不再赘述。

下面我们继续聚精到例题。

P3041 [USACO12JAN] Video Game G

给你 m 个文本串 T_1,T_2,\dots,T_m，构造一个长度为 n 的字符串 S，使得 S 中出现 T_1,T_2,\dots T_m 的数量尽可能的多。输出这个出现次数。1\le n\le 20,1\le m\le 10^3,1\le |T|\le 15,T_{i,j}\in{\texttt{A,B,C}}。

考虑 dp_{i} 表示前 i 个位置上的最大价值。

但是这个好像不能转移，注意这个的转移跟整个串有关，因此考虑建出 Trie，然后增加一维 dp_{i,j} 表示前 i 位，且当前结尾在 Trie 上第 j 个节点的答案。

则有 dp_{i+1,x}=dp_{i,u}+v_{x}(x\in son_u)，其中 v_x 表示根节点到 x 路径上经过的字符组成的字符串 P 在 T 中出现的次数。

如果你直接转移那么你显然错了，因为 P 所带来的贡献并不只有 P 本身，还有 P 的所有后缀在 T 中出现的次数。

我们很容易想到 AC 自动机：因为 AC 自动机的 nxt 节点的定义就是这样的，我们只需要不断往上跳 nxt 节点就可以找到所有的贡献了。

P2292 [HNOI2004] L 语言、

求 S 的最长前缀 S'，使得 S' 可以由词典 T 中的串组成，有 m 组多测。1\le |T|\le 50,1\le |T_i|\le 20，1\le |S|\le 2\times 10^6,1\le m\le 50。

注意作者的题意与原题中的 S,T 是反过来的。

定义 dp_i 表示 1\sim i 是否能成为一组解，则有 dp_i=|_{1\le j<i\land f(j+1,i)=1}dp_j。其中 f(j+1,i) 表示 S_{j+1\sim i} 是否在 T 中，负责度 O(m|S||T|^2)。

显然你不用每次匹配都从头开始，考虑 j 从后往前遍历，然后将词典 T 翻转，这样 j 的转移就可以在 Trie 上跳跃了。时间复杂度 O(m|S||T|)，只有 80 分。

我们先转换一下，将填表法变成刷表法，从 dp_i 往后推，这样就不用翻转字符串了，可以直接进行递推，复杂度仍然是 O(m|S||T|)。

注意到 T_i 只有 20，也就是说我们真正转移的有效区间的长度也只有 20，我们考虑状压。

我们定义 f_p 表示在 Trie 上的第 p 个节点可以由哪些长度转移，由于最多转移的长度只有 20 个，所以可以用一个整数存下。

如果知道了 f 数组，则最终的答案可以直接将原串在 Trie 上跑，如果当前的状态 now 与 f_p 与起来不为 0 说明一定可以从一些点转移过来，则 now=now\times 2+1，否则 now=now\times 2。

注意到 f 数组的转移是以后缀合法字符串的形式转移得到的，我们考虑使用 AC 自动机，因为 nxt 指针可以快速的帮我们找到上一个后缀，转移时或起来即可，时间复杂度 O(m|S|+\sum |T|)。

P4052 [JSOI2007] 文本生成器

给你一些文本串 S，求有多少个长度为 n 的 T，使得 T 至少有一个子串在 S 中出现过。答案对 10^4+7 取模。

至少一个子串在 S 中出现过是困难的，考虑正难则反，找到所有 T 满足其的所有子串在 S 中都没有出现过的个数 x，然后答案即为 26^n-x。

考虑 dp_i 表示长度为 i 的且其子串不在 S 中出现过的个数。

这样是很难转移的，我们考虑 dp_{i,j} 表示长度为 i，且现在在 Trie 上第 j 个节点的方案数。

则显然有转移 dp_{i+1,son_j}=dp_{i,j}。

但是你需要判断 dp_{i,j} 的合法性，也就是说，从根到 j 组成的字符串不在 S 中出现，由于我们已经建出了 Trie，这个条件等价于 Trie 上第 j 个节点的所有后缀不在 Trie 中作为末尾元素出现。这个很自然的想到 AC 自动机。因为 AC 自动机可以快速处理所有后缀的转移，转移时使用或即可。

P9613 [CERC2019] K==S

给你一些文本串 S，求有多少个长度为 n 的 T，使得 T 任意一个子串在 S 中都没有出现过。答案对 10^9+7 取模。1\le n\le 10^9。

这个题乍一看和上一个题一样，但是这个题的 n 特别大，无法直接处理。

我们建出 AC 自动机，然后可以得到每一个点是否满足其后缀不在 T 中，设这个值为 f=0/1。

我们分析一下，相当于就是从根节点到某一个节点不经过任何 f=1 的节点，要经过 n 次的方案数。

显然这是一个矩阵快速幂的板子题，考虑定义 dp_{i,j} 表示 i\to j 经过若干条边的方案数。一开始只能经过 1 条边，可以通过 AC 自动机预处理。

然后直接跑矩阵快速幂，时间复杂度 O(|T|^3\log n)。

P3502 ^{*} [POI 2010] CHO-Hamsters 不知道是削弱还是加强版

给你 n 个串 S_1,S_2,\dots S_n，构造一个长度最小的串 T，使得 T 中出现 S_1,S_2,\dots S_n 的次数之和至少为 m，\sum |S_i|\le 100,m\le 10^{18}，**不保证对于任意 x,y，其中 S_x 不是 S_y 的子串。

考虑 dp_{i,j} 表示出现次数为 i，且现在在 Trie 上第 j 个节点的最短字符串的长度。

则有 dp_{i+val_{son_j},son_j}=dp_{i,j}，其中 val_{son_j} 表示 Trie 上根到 son_j 组成的字符串作为结尾出现了多少次，这个可以用 AC 自动机跑出。

但是这个题的 m 特别大，考虑矩阵优化。

注意到转移相当于是 j\to son_j 连了一条权值为 val_{son_j} 的边，你需要求从根开始要经过 m 的边权，需要经过的最少边数是多少，显然直接使用 (\min,+) 矩阵优化。这样的话复杂度是 O(S^3\log n)，S 的状态过大，原题无法通过，削弱版削弱了 |S| 的长度，可以通过。