/kel
by Qiuly @ 2020-06-18 17:11:11
qp%Qiuly
by 出言不逊王子 @ 2020-06-18 17:17:41
@[Qiuly](/user/113190) 一个串的循环节是 $n - fail _n$，如果 $fail _n > \frac n 2$ 那么这个串就会至少有一个出现次数大于两次的循环节
by EndSaH @ 2020-06-18 17:22:44
都有循环节了 check 这个循环节多遍没啥意义，直接 check 第一个循环节即可
by EndSaH @ 2020-06-18 17:25:33
就是说当前串的 max Border 的长度大于了当前串的一半。
那么原串的构造就是一些相同的串然后最后跟个小尾巴（也可能没有小尾巴
令 $T$ 为一个字符串，$P$ 为小尾巴，$S$ 为当前串。假设 $S$ 等于 $nT+P$ ，这里 $nT$ 的意思就是 $n$ 个 $T$ 。
那么还有必须满足的就是 $P$ 是 $T$ 的一个前缀。
然后跳 $fail$ 的时候第一次会跳到第一个 $T$ ，也就是 $nT+P$ 跳到了 $(n-1)T+P$ ，但是接下来跳的 $(n-2)T+P$ 以及之后的都没有意义了，因为串后面接的元素都是相等的，所以直接跳到 $P$ 就好了？
by Qiuly @ 2020-06-18 17:32:46
@[EndSaH](/user/91252) /kel
by Qiuly @ 2020-06-18 17:33:03
```cpp
qiulyqiulyqiulyqiulyqiu(?)
qiulyqiulyqiulyqiu(l)
qiulyqiulyqiu(l)
qiulyqiu(l)
qiu(l)
```
这样的话对于第一个串只需要计算后面的`?`是否合法吧 /kel
然后`l`的贡献直接在`qiu`算嘛 /kel
在最短的地方算不太对吧 /kk
by Qiuly @ 2020-06-18 17:37:49
所以当发现有出现次数大于 $1$ 的周期时直接算最长的那个的贡献，然后跳到最短的 $nxt$ 好了 /yiw
by Qiuly @ 2020-06-18 17:51:38
@[Qiuly](/user/113190) 你说的是对的。
先尝试跳一步，然后不匹配直接将位置对循环节长度取模。注意特判取模成零的情况。（请忽视我一开始说的东西
我这里没 check 串后的位置是因为在上次跳的时侯已经 check 完毕了
by EndSaH @ 2020-06-18 19:52:33
嗯，thx
by Qiuly @ 2020-06-18 20:35:59