「OI之路」06字符串-1KMP

KMP

板子:

1
2
3
4
5
fo(i,2,n)
{
int j=nxt[i-1];while(j and A[j+1]!=A[i]) j=nxt[j];
nxt[i]=j+(A[j+1]==A[i]);
}

陶陶的名字(可以重叠的最小覆盖)

最小覆盖

upd:不记得下面在写啥了,但其实如果你会border那套理论的话就没啥了

参考文献:FarmerJohn

定义:
对于一个字符串,一个长度最小的满足
「复制自己多次(不重叠,与陶陶的名字不同)后可以覆盖原串」的子串

结论:
长度=n-next[n]

证明:
先证明它是覆盖子串
①next[n]<=n-next[n]

显而易见覆盖

②next[n]>n-next[n]

然后它也是最小的
这里用反证法,假设存在一个比n-next[n]更小的C(所以蓝色>0),然后截取掉
强行定义一个黄色段,是C的补集,然后因为C会最小覆盖,所以是C的前缀

这样的话,黄色部分比next[n]更长,不满足next[n]是最长这个定义

Q.E.D.

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c111.html
转载请注明出处,谢谢!