妙啊

5:41 p[1~next[i] 应该是和 p[i-next[i]+1~i] 是相等的吧

设字符串a[1~n]长度为n.
这里的n % (n - nxt[n]) != 0则不存在非平凡循环节的推断不那么显然吧。
事实上我们定义$p$是一个“周期”，当且仅当$a_i = a_{i + p}$ (对$\forall i < n - p$ 成立)
定义$q$是一个“完美周期”，当且仅当n%p==0

那么当$p+q \le n$时候，若$p$是周期，$q$是周期，则$|p - q|$也是周期，从而$p$ % $q$也是周期，因此gcd(p, q)是周期。

注意到p = n - nxt[n]是一个周期，若p不完美，我们要证不存在完美周期。
反证：设完美周期为q>p(nxt性质)，则有q <= n / 2，则p+q<=n, 于是gcd(p, q)是完美周期，且gcd(p, q)<=p也是周期，且为完美周期，矛盾。

证明一下最后说的“显然不成立”的部分。

淦！14.23秒y总表示不能用字符串hash代替这种情况 我就写了半个小时的字符串hash 呜呜呜

hhh

强烈建议把这道题加到基础课里面 呜呜 今天考这个题没写出来 在这看到了

这道题目不基础呀hh 可以考虑放到提高课里。