P3041 [USACO12JAN]视频游戏的连击Video Game Combos 可以想到，用 dp(i,j)dp(i,j)dp(i,j) 代表输入字符串长度为 iii ，匹配到节点 jjj 时可以达到的最大分数。 我们有 dp(i,ch(j,k))=min⁡{dp(i−1,j)}dp(i,ch(j,k))=\min\lbrace dp(i-1,j)\rbracedp(i,ch(j,k)...

首先，观察到 n≤12n \le 12n≤12 ，可以想到状压，我们用 f(u,sta)f(u,sta)f(u,sta) 表示可不可能走到 AC 自动机上节点 iii ，并且状态为 stastasta 的字符串已经是现在串的字串。并且，通过 BFS ，我们可以保证串的长度最短。 关键在于如何找出方案，我们记录 pre(u,sta)pre(u,sta)pre(u,sta) 二元组，代表 f(u...

AC 自动机 = KMP + Trie