一、概要：
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的(先了解BF算法)。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
二、怎么求模式串next[n]的值：
定义：
（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
举例：
01）求T=“abcac”的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据 (4) 因（3）有1<=k<j;不能说，j=1,T[j-1]==T[0]
next[2]=0 根据 (4) 因（3）有1<=k<j;（T[0]=a）!=（T[1]=b）
next[3]= -1 根据 (2)
next[4]=1 根据 (3) T[0]=T[3] 且 T[1]=T[4]
即
|
下标 |
0 |
1 |
2 |
3 |
4 |
|
T |
a |
b |
c |
a |
c |
|
next |
-1 |
0 |
0 |
-1 |
1 |
若T=“abcab”将是这样：
|
下标 |
0 |
1 |
2 |
3 |
4 |
|
T |
a |
b |
c |
a |
b |
|
next |
-1 |
0 |
0 |
-1 |
0 |
为什么T[0]==T[3],还会有next[4]=0呢, 因为T[1]==T[4], 根据 (3)” 且T[j] != T[k]”被划入（4）。
02）来个复杂点的，求T=”ababcaabc” 的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据(4)
next[2]=-1 根据 (2)
next[3]=0 根据 (3) 虽T[0]=T[2] 但T[1]=T[3] 被划入（4）
next[4]=2 根据 (3) T[0]T[1]=T[2]T[3] 且T[2] !=T[4]
next[5]=-1 根据 (2)
next[6]=1 根据 (3) T[0]=T[5] 且T[1]!=T[6]
next[7]=0 根据 (3) 虽T[0]=T[6] 但T[1]=T[7] 被划入（4）
next[8]=2 根据 (3) T[0]T[1]=T[6]T[7] 且T[2] !=T[8]
即
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
T |
a |
b |
a |
b |
c |
a |
a |
b |
c |
|
next |
-1 |
0 |
-1 |
0 |
2 |
-1 |
1 |
0 |
2 |
只要理解了next[3]=0，而不是=1，next[6]=1，而不是= -1，next[8]=2，而不是= 0，其他的好象都容易理解。
03) 来个特殊的，求 T=”abCabCad” 的模式函数的值。
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
T |
a |
b |
C |
a |
b |
C |
a |
d |
|
next |
-1 |
0 |
0 |
-1 |
0 |
0 |
-1 |
4 |
next[5]= 0 根据 (3) 虽T[0]T[1]=T[3]T[4],但T[2]==T[5]
next[6]= -1 根据 (2) 虽前面有abC=abC,但T[3]==T[6]
next[7]=4 根据 (3) 前面有abCa=abCa,且 T[4]!=T[7]
若T[4]==T[7]，即T=” adCadCad”,那么将是这样：next[7]=0, 而不是= 4,因为T[4]==T[7].
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
T |
a |
d |
C |
a |
d |
C |
a |
d |
|
next |
-1 |
0 |
0 |
-1 |
0 |
0 |
-1 |
0 |
如果你觉得有点懂了，那么
练习：求T=”AAAAAAAAAAB” 的模式函数值，并用后面的求模式函数值函数验证。
意义：
next 函数值究竟是什么含义，前面说过一些，这里总结。
设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
1. next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0]
2. next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。
3. next[n]= k >0 但k<n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？
4. 其他值，不可能。
三、代码：
1 <?php 2 //求next值 3 function get_nextval($s) 4 { 5 $next[0] = -1; 6 $j = 0; 7 $k = -1; 8 9 $length = strlen($s); 10 while($j<$length-1) 11 { 12 if($k==-1 || $s[$j]==$s[$k]) 13 { 14 ++$j; 15 ++$k; 16 if($s[$j]!=$s[$k]) 17 { 18 $next[$j] = $k; 19 } else { 20 $next[$j] = $next[$k]; 21 } 22 } else { 23 $k = $next[$k]; 24 } 25 } 26 return $next; 27 } 28 29 function kmp($s, $t, $pos=0) 30 { 31 $i = $pos; 32 $j = 0; 33 $slength = strlen($s); 34 $tlength = strlen($t); 35 $next = get_nextval($t); 36 $index = 0; 37 while($i<$slength && $j<$tlength) 38 { 39 if($s[$i]==$t[$j]) 40 { 41 $i++; 42 $j++; 43 } else { 44 if(-1==$next[$j]) 45 { 46 $i++; 47 $j = 0; 48 } else { 49 $j = $next[$j]; 50 } 51 $index = $i; 52 } 53 } 54 if($j == $tlength) 55 { 56 return $index; 57 } else { 58 return false; 59 } 60 } 61 62 $t = "abCabCad"; 63 $s = "abCabCaabCabCad"; 64 $index = kmp($s, $t); 65 var_dump($index);