【KMP】从前后缀理解KMP

Border 和 周期

  • 周期的定义:

    (0<p<|s|, s[i] = s[i+p], forall i in{1,2,...,∣s∣? p})周期不能为0,也不能等于串长.

  • Border:

    (0<r<|s|, pre(s,r) = suf(s,r)), 则pre(s,r)为s的一个border(公共前后缀) 易得(|s|-r)为周期。

  • Border的性质

    传递性:s为t的border,t为r的border,则s为r的border

    强传递性: s为r的border,长于s的串t也为s的border,则s为t的border

    (mb(s)) 为s的最长border长度,则$pre(s,mb(s)),pre(s,mb(mb(s))).... $构成了s的所有border。这条性质由强传递性可得。

KMP

给定模式串s和文本串t,求s在t中出现了多少次

  • next数组

    实质:每个前缀的最长border长度。

    定义:next[i] = mb(pre(s,i)) 、

    求解:假设pre(s,j)为pre(s,i)的border, 则 s [1~j] = s [i-j+1,i], 则 s[1~ j-1] = s[i-j+1 ~ i-1]且

    s[i] = s[j]. 即 pre(s,j-1) 为 pre(s,i-1) 的border且 s[j] =s[i].

    我们从next[i-1]递推next[i], 实际就是pre(1,i-1)的符合s[k+1] = s[i] 且最长的border k。

  • 匹配过程

    把满足t[i-k+1~i] = s[1~k]的k称为一个i位匹配长度。当i=n,匹配成功一次。

    设k1<k2为第i位的两个不同的匹配长度,s[1 to k1] = t[i-k1+1 to i] ,s[1 to k2] = t[i-k2+1 to i]

    由于s[1 to k1] 为 s[1 to k2] 的前缀,t[i-k1+1 to i]为t[i-k2+1 to i]的后缀,所以pre(s,k1)是pre(s,k2)的border。

    由于s[1 to k] = t[i-k+1 to i]等价于 s[1 to k-1] = t[i-k+1 to i-1] 且s[k] = t[i].

    所以i位的最大匹配长度是由i-1位匹配长度推得。

    那我们尽量找一个大的i-1位得匹配长度k,使得s[k+1] = t[i]. 这就是next跳转的原因。

  • 字符串最小周期。

    n - 最长border长度next[n].

    像OIwiki那样从前缀函数的角度理解也挺好。

【KMP】从前后缀理解KMP

原文地址:https://www.cnblogs.com/Cha2azzZ/p/13449929.html