KMP模版

-------------------------------------------------------------------------------------

KMP的失配数组 f 含义:

    i  0  1  2  3  4  5  6  7  8  9  10  11

P[i] a   b  r  a  c   a  d  a  b  r   a    无

f[i]   0  0  0  0  1  0  1  0  1  2  3    4

仔细观察就能得出 f 数组的含义：字符串 P  的前缀与 i位置的后缀的最大匹配字符个数-1。

比如第10号位置

P: ABRA······

    ······ABRA

1、此时f[i] = 最大匹配字符个数-1. 

2、也是第二个字母A在 P中的下标。

 循环节概念：

如字符串 P = "ABCABCABCABC"

则这里的循环共有3个： 1、ABC 2、ABCABC 3、ABCABCABCABC

就是把一定长度的前缀重复数次就能得到自身。

而 ABC 又叫最小循环节

再看失配数组：

    i  0  1  2  3  4  5  6  7  8  9

P:    a  b  c  a  b  c  a  b  c  无

f:     0  0  0  0  1  2  3  4  5  6

---

先给出结论：

如果 i % (i-f[i]) ==0 则=>字符串P[0-i] 这段的字符串的最小循环节一定是{ {P[0],P[1],P[ i-f[i] ]}, {P[i-f[i]+1,···}

也就是说 P[0-i] 最小循环节长度为  i - f[i]

比如 i==5时字符串P[0-i]为：abcabc,  i - f[i] = 3 ,即abc

比如 i==8时字符串P[0-i]为：abcabcabc,  i - f[i] = 3 ,即abc

----

证明：

1、循环节长度

比如字符串长度为16 那么，循环节长度只可能是 1,2,3,4,8,16.（当然自身是自身的循环节没啥意思，忽略16，那么剩下的就是16的因子）

设ABCD长为16，每段长度为4。

当i==16时，f[i] = 12.

满足等式 i % (i-f[i]) == 0。

由f[i] 含义得到前12个字符和后12个字符相同。

因为12 % (i-f[i])同样=0，所以把12分成 12/(i-f[i]) 份，即分成3份。

再由ABC = BCD =:> A=B && B=C && C=D.

由等式连等得到 A=B=C=D

循环节证毕。

----------------------------------

我们想象一下KMP函数的执行过程：

                   i

                   ↓

S1：ACM MECKSDLF

S2：ASFDJKLEDHV

f2：01349098203045 //乱写的

             ↑

              j

显然i是不停→移动，而j是不停进行失配过程。

则当i移动到S1结尾时，j所在的位置就是j所失配的位置。（注意此时i是超过S1的（在最后一个字母后面一位, 且j不一定与S1[i]匹配 ，但S2[j]（不包括S2[j]前面的一定与S1匹配）

而pos 是S2的前缀与S1的后缀最大匹配字母数。 因此S2[pos]是不与S1匹配的！

-----------------------------------------

失配数组优化：