KMP

 

s[1~nxt[i]]不是周期串  s[1~i]也不是周期串

s[1~nxt[i]]是周期串  s[1~i]也是周期串

两个相同的周期串首尾重叠在一起,重叠位置一定是一个周期的开头?

重复覆盖

ababababa 可以被aba重复覆盖

不重复覆盖

abababab可以被ab重复覆盖

交叉覆盖:既有重复覆盖又有不重复覆盖

ababaaba 可以被aba交叉覆盖

重复覆盖与不重复覆盖之间奥妙重重,其本质如下

重复覆盖  A: ___^^^___^^^___^^^___^^^___

不重复覆盖   B: ___^^^___^^^___^^^___^^^

因此对于如下情况

___________

___________

两段绿色的字符相等,假设绿色的字符串即s[1~nxt[i]]能最小被len长度的字符串重复覆盖

那么s[1~i]肯定也能被len长度的字符串覆盖,但是不会被更短长度的字符串覆盖

只有从交替式的非周期串变成了周期串才有可能使得答案变得更短。即从上面的A 变成 B

但是 假如s[1~nxt[i]]不是周期串  s[1~i]就不可能是周期串。因为假如s[1~i]是周期串,s[1~nxt[i]]就一定是周期串

所以无法变成周期串,无法使答案变得更小

当nxt[i] < i/2的时候,nxt[i]往后只能通过交叉覆盖的方式覆盖到 i,因为其他两种覆盖方式都不会导致nxt[i] < i/2

abcab abc abcab

如果能覆盖到i,肯定也能覆盖到 i - ans[nxt[i]] ~ i - 1 之间的某个位置,所以维护每一个ans所能覆盖到的最右端的位置就好了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注