2019 ECNU XCPC April Selection 2

2019 ECNU XCPC April Selection 2

开始算法专题场。

如果做的很不顺手的，需要阅读相关资料来提高。

推荐阅读

[字符串相关算法学习总结]

我自己写的这篇文章仅包含基础的三个匹配算法及其应用。

Problem C

涉及算法：KMP。

对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。

于是最大的循环节就是最后一个$Next$嵌套中$Next[y]=0$的前缀$y$。

不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。

Problem D

涉及算法：最小表示法。

模版题。

自行查阅资料。

Problem E

涉及算法：AC 自动机 + dp 。