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 呜呜呜
强烈建议把这道题加到基础课里面 呜呜 今天考这个题没写出来 在这看到了