具体解法见LYD蓝书
这里主要讲一下为什么只用判断\(next[i]\),而不用继续判断\(next[next[i]]\)或者\(next[next[next[i]]]\)等等
主要是有以下几个结论:
如果\(s[1\)~\(i-next[i]]\)不能作为\(s[1\)~\(i]\)循环元,那么\(s[1\)~\(i-next[?]]\)也都一定不能作为\(s[1\)~\(i]\)的循环元
如果\(i-next[i]\)不可整除\(i\),\(s[1\)~\(i]\)一定不存在循环元。
如果\(i-next[i]\)不可整除\(i\),\(i-next[?]\)也都一定不可整除\(i\)。
如果\(s[1\)~\(m]\)是\(s[1\)~\(i]\)的循环元,\(next[i]\)一定为\(i-m\)(\(i-m\)一定为\(next[i]\))。(在算法竞赛进阶指南上有这么一句话:如果\(s[1\)~\(m]\)为\(s[1\)~\(i]\)的循环元,\(i-m\)一定是\(next[i]\)的“候选项”,与此处意义略有不同)
若\(m=i-next[i]\),\(j=next[?]\),\(next[j]=j-m\)。(无论\(m\)可否整除\(i\))(由④扩展而来)
以上结论来自这篇文章
标签:周期,不可,next,如果,循环,一定,整除 From: https://www.cnblogs.com/dingxingdi/p/17968426