Today , 第一次学习KMP Algorithm，其中好多地方还是不能理解的透彻，本文将进一步对 KMP Algorithm 进行学习，搞清楚其中的思想……
First , KMP Algorithm is best known for liner time for exact matching , (Runing time is O(Length(S)+Lendth(P))) Because Preprocessing is O(P) , Matching is O(Length(S)) , 效率很 high , 成功的避免了Recomputing Matches ;
若想 Avoid Recomputing Matches , 就需要 Preprocessing ，对于 Preprocessing ，就是找出字符串P中的 Repeat char can backtrack position by prefix-function;
字符串P为：
| a | b | a | b | a | c | a |
字符串S为：
| b | a | c | b | a | b | a | b | a | b | a | c | a | a | b |
定义两个指针 i 和 j ，i 是指向 字符串 S 中的第 i 个数据元素 ， j 是指向字符串 P 中的第 j 个数据元素 ，用指针 i 和 j 分别表示 S[ i - j + 1 , …… i ] 和 P[ 1 , …… j ] 中的数据元素完全相等， 随着 i 的值不断增加 ， j 的值也在不断变化 ，通过对字符串 P 进行 Preprocessing 得到 next数组 ，j 的值变化有两种可能：1、如果 P[ j + 1 ] 与 S[ i + 1]相等，j 应该加 1 ； 2 、如果 P[ j + 1 ] 与 S[ i + 1 ] 不相等 ，则 j 应该等于 next 数组中第 j 个数据元素的值 ；next 数组就是用来记录 当P[i + 1] 与 S[ j + 1 ] 不相等时 ， j 的变化 ；
下面介绍一下，Prefix - function ，即如何确定next 数组 ；
m ← Length[ P ] ;
k = 0 ;
next[1] ← 0 ;
for q ← 2 to m do
while k > 0 and p[k+1] ≠ p[q] do
k = next[k] ;
end while
if(p[k+1] = p[q] )
k ← k + 1 ;
end if
next[q] = k ;
end for
这样即可得到 nex t数组 ；
得到 next 数组之后，就可进行字符串P 与 字符串S 进行匹配了 ，具体匹配过程，下面给出相应的伪代码：
n ← Length[ S ]
m ← Length[ P ]
k = 0 ;
for i ← 1 to n do
while k > 0 and p[ k+1 ] ≠ S[ i ] do
k = next[ k ] ;
end while
if p[k+1] = S[i] then
k ← k + 1
end if
if k == m then
return true
end if
end for
Knuth-Morris-Pratt Algorithm,布布扣,bubuko.com
原文：http://www.cnblogs.com/scottding/p/3603527.html