【文文殿下】浅谈KMP算法next数组与循环节的关系

Syameimaru 2018-10-22 原文

KMP算法

KMP算法是一种字符串匹配算法，他可以在O(n+m)的时间内求出一个模式串在另一个模式串下出现的次数。
KMP算法是利用next数组进行自匹配，然后来进行匹配的。

Next数组

Next数组表示一个前缀的最长proper的长度。
简单地讲，$S[1~next[i]] = S[next[i]+1~i] $.

循环节

一个字符串$S$，若是由字符串$P$重复$k(k>1)$次形成的，则称字符串$P$是$S$的一个循环节。使$k$最大的循环节被称为最小循环节。

引理：

对于一个字符串的前缀$S[1~i]$，它存在一个长度为$len$的循环节，当且仅当$len|i$,$len<i$,且$S[1~len]=S[len+1~i]$.
即$len$为$S[i]$的一个$proper$长度且$len$整除$i$.
显然，当$len$取$i-next[i]$时，求得的循环节为最小循环节。通过$next$数组的不断迭代，可以求出前缀$S[i]$的所有循环节。

对于引理的证明

先证必要性。设$S[1~i]$具有长度为$len$的循环节，显然$len$整除$i$,并且$S[1~i-len]$和$S[len+1~i]$都是由$i/len-1$个循环节构成的。故$S[1~i-len]=S[len+1~i]$.
再证充分性。设$len$整除$i$，并且$S[len+1~i]=S[1~i-len]$，因为$len<i$，所以$S[1~i-len]$和$S[len+1~i]$的长度不小于$len$且是$len$的倍数。各区前$len$个字符，有$S[1~len]=S[len+1~2*len]$,可以发现，他们是以$len$为间隔错位对齐的。故$S[1~len]$是$S[i]$的一个循环节。