CF461E Appleman and a Game
题意有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。题解显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪...
题意有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。题解显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪...
作为菜鸡 OIer，本文尽量用通俗的语言去讲解后缀自动机。当然学习后缀自动机前是有一点点前置知识的，我一块给说了。有限状态自动机（DFA定义确定优先状态自动机 $\mathcal{A}$ 是由：一个非空有限的状态集合 $Q$一个输入字母表$\Sigma$ （非空有限的字符集合）一个转移函数 $\delta :Q\times \Sigma \rightarrow Q$（例如：$\delta \...