Difference between revisions of "2019 ECNU XCPC April Selection 2"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 8: | Line 8: | ||
== Problem C == | == Problem C == | ||
| + | |||
| + | 涉及算法：KMP。 | ||
对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。 | 对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。 | ||
Revision as of 05:02, 6 April 2019
2019 ECNU XCPC April Selection 2
Problem A
Problem B
Problem C
涉及算法：KMP。
对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。
于是最大的循环节就是最后一个$Next$嵌套中$Next[y]=0$的前缀$y$。
不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。