链接：SPOJ、洛谷。
大意：给你一些关键词 S[]，然后让你构造一个指定长度的字符串 T（都只有 ABC 三种字符），使每个 S[i] 在 T 中的出现次数的和最大，并且输出这个数值。
首先这道题可以用 DP，因为我们肯定要枚举 T 的长度，所以我们可以把 f 加一维 i，用 f[i] 表示前 i 个字符。
然后因为每个 S 的长度不超过 15，为了转移，我们要把这 15 个字符记录为一个状态，总数为 $3^{15}$ 个，也就是用 f[i][j] 表示在前 i 个字符中，以 j 结尾的最大匹配次数为多少。
这样的状态我相信你们随便推一推就可以推出来，所以这里不细讲了。
如果真的按照上面那种做法的话，那么时间复杂度便是 $O(n \times 3^{15} \times 3)$，非常危险（空间也是）。可不可以优化一下呢？
我们可以想，要优化 DP 无非就是要削减状态数或是优化转移方程两种方法而已。转移方程每次只要考虑 3 种字符的情况即可，优化空间较小。
但是转移方程记录那么多真的有用吗？不一定。
我们可以想，记录 $3^{15}$ 的状态真的有用吗？拿样例来举例子吧，例如：
3 7
ABC
CB
ABBCB
假如我们有一个状态是 CCCCC，记那么多有用吗？显然没有，因为 CCCCC 在现在和将来都不能对答案有贡献，也就是不能构成新的串，所以 CCCCC 是一点用都没有的。
既然有一些状态没有用，所以我们就可以想：哪些状态是有用的呢？
显然，能在以后对答案有贡献的状态都是有用的。而且，能在以后组成 S 的状态一定都是 S 的前缀，对于样例，A、ABAC、C 都可能对答案有贡献。所以我们的状态就可以压缩成非常小。
然后，我们如何转移呢？
我们考虑一个状态：AB，再加一个字符就可以组成 ABA、ABB、ABC。
ABA，ABA 本身（整个）是不能对答案有贡献的，所以它的后缀 A 可能对答案有贡献（ABC 或 ABBCB），所以我们就去掉 AB，保留后缀 A，让 A 成为一个新的状态；ABB，它可以对 ABBCB 有贡献，所以我们要保留整个 ABB；ABC，与 1 同理，只用剩下 C 即可。这样做就可以大幅减少时间和空间使用了。
看完上面整个过程，有些人可以觉得与 AC 自动机有些类似。
没错！它就是 AC 自动机，上面保留前缀的过程就是 AC 自动机上的点，抛弃无用的前缀则与 AC 自动机的匹配过程非常类似。
所以我们可以用 f[i][j] 表示在前 i 个字符中，在 j 节点时的最大匹配次数为多少。然后转移就是想 AC 自动机匹配时那样转移即可。
最后统计 f[k][i] （i 为所有节点）的和即可。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：[SPOJ] Video game combos”