String
给定两个字符串 \(a\), \(b\), 我们称这两个字符串的所有子序列为坏字符串。求最短的非坏字符串。
做法：
首先要解决一个问题，假设你有一个字符串你需要判断这个字符串是否是坏的，怎么快速判断？
我们预处理出 nxta[i][j] 表示 \(a\) 字符串中第 \(i\) 个位置之后第一个 \(j\) 字符出现的位置。
\(b\) 字符串同理。
我们判断时只需要扫一遍当前的字符串，并用 nxt 数组在 \(a\), \(b\) 上跳，如果都跳出去了，那么就是好串，反之坏串。
那么怎么算最短的这个串呢？
考虑 \(\text{dp}\)。
f[i][j] 表示最短的最后一位等于 \(a[i]\), \(b[j]\)，的字符串长度。
假设当前字符串 \(a\) 枚举到位置 \(i\)， \(b\) 枚举到位置 \(j\)，第 \(i + 1\) 位填 \(x\)，转移式子： f[nxt[i + 1][x]][nxt[j + 1][x]] = f[i][j]。最后我们要的答案就是 f[n + 1][m + 1]。
但是这个很对的做法，时间复杂度是 \(O(26 \times n^2)\)，只能获得 \(80\) 的高分。
\(100\) 分也很简单啊，直接将答案和第 \(2\) 位交换一下，注意到答案不会超过 \(\frac{n}{26}\)。
那么我们的转移式子要改变一下，假设当前字符串 \(a\) 枚举到位置 \(i\)，答案字符串长度为 \(j\), 下一位 \(x\)：
f[nxt[i + 1][x]][j + 1] = max{nxt[f[i][x] + 1][x]}。最后只要判断 f[i][j] >= m+1 是否成立即可。