【KMP】从前后缀理解KMP

Border 和 周期

• 周期的定义：

  \(0周期不能为0，也不能等于串长.

• Border：

  \(0, 则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

  由于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那样从前缀函数的角度理解也挺好。