题意

求字符串每一个前缀的最长循环节长度之和。

分析

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

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

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

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注