XI Open Cup. Stage 3. Grand Prix of Azov Sea 题意：有一个字符串 $S$ 和 空字符串 $T$ ，每次操作可以在 $T$ 后面加一个字符，或者删掉一个字符。每次操作完之后，所有在 $S$ 中匹配位置会高亮。求最小操作次数，把 $S$ 里的所有位置都至少高亮一次。
$1 \le |S| \le 10^5$
题解：令 $m$ 是字符集大小，那么答案肯定是不超过 $2m-1$ 的。因为我们总是可以打一个字符，然后删一个字符，这样操作着把所有字符都打一遍，显然所有位置都会被高。由于最后一个字符不需要删除，操作次数是 $2m-1$ 。
那么接下来可以断言，一定存在一个最优的操作序列类似：加一个字符，删一个字符；加一个字符，删一个字符；……；加字符，加字符，……，加字符。也就是说除了最后连续的加字符，其他任意时刻，$T$ 要么是空串，要么是一个字符。
证明比较容易，考虑调整法即可。假设某个最优操作过程，删字符前的字符串依次为 $x_1,x_2,\dots,x_k$ 。考虑 $x_1$ 和 $x_2$ 的最长公共前缀长度 $l$ ：
如果 $l=0$ ，那么显然我们需要执行 $|x_1|$ 次加和 $|x_1|$ 次删，才能便会成空串。这个不如直接搞成把 $x_1$ 的每个不同的字符加一次，删一次，答案肯定不会变劣。
如果 $l \ge 1$ ，那么考虑 $x_1$ 中除去最长共前缀的部分，显然也可以把里面每个不同字符拿出来，加一次，删一次。答案也不会变劣。
依次类推，我们可以把 $x_1, x_2, \dots, x_{k-1}$ 都拆成单个字符。
如一开始所说，$x_k$ 的长度也满足 $\le 2m-1$ 。因此，我们可以枚举每个长度不超过 $2m-1$ 的子串作为 $x_k$ 。知道 $x_k$ 后来求答案就方便了很多，我们仅需要知道还有多少个不同字符没有被覆盖即可。也就是说，需要求出在依次加入 $x_k$ 每个字符的时候，总共覆盖了多少个不同的字符。
令 $cnt(c)$ 表示字符 $c$ 在 $s$ 中出现的次数，然后建出 $s$ 的后缀自动机。那么对于 $x_k$ 的每个前缀$x_k[1..i]$，我们可以在自动机中找出对应的节点 $v_i$ ，也能知道这个串出现了多少次 $w_i$ 。如果不存在一个$x_k[1..i-1]$ 的前缀是 $x_k[1..i]$ 的后缀，也就是没有 border，那么有 $w_i$ 个字符 $x_k[i]$ 被新覆盖了。我们可以令 $cnt(x_k[i]) = cnt(x_k[i]) - w_i$ ，当 $cnt(x_k[i])$ 变成 $0$ 的时候，就有一个字符被完全覆盖了。这个时候就可以更新一遍答案。
枚举 $x_k$ 的时候，我们仅需要枚举子串的起点 $l$ 即可，然后在自动机上走不超过 $2m-1$ 步。因此复杂度是 $O(|S| \cdot m)$ 。