Description
两个字符串 \(A\) 和 \(B\),若 \(A\) 是 \(B\) 的前缀且 \(A\ne B\),则称 \(A\) 是 \(B\) 的 proper 前缀。
两个字符串 \(C\) 和 \(D\),若 \(C\) 是 \(D\) 的 proper 前缀且 \(D\) 是 \(CC\) 的前缀,则称 \(C\) 是 \(D\) 的周期。
给出一个字符串,求它的所有前缀的最大周期长度之和。
Solution
这题有点构造那味了。
首先我们要明确,此周期非循环节,而是一个 proper 前缀,同时我们又需要他尽量长,所以我们可以只留下一个最短公共前后缀,剩下的都作为 proper 前缀。
这样一来,此 proper 前缀自己循环一遍后,自己留下的最短公共前后缀接到了自己的后边,恰好可以和原串匹配,所以可以保证循环一次以后照样可以匹配。
我们又知道 \(\text{nxt}[i]\) 的性质可以找最长公共前后缀,所以处理出 \(\text{nxt}\) 并不断向前递归即可找到最短公共前后缀。