KMP字符串模式匹配算法详解2009-09-04 19:28个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的，另外有关模式函数值nexti确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数 f(j)的说法，其实是一个意思，即nextj=f(j-1)+1，不过还是nextj这种表示法好理解啊： KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。一.简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S , char T , int pos ) /* 若串 S 中从第pos(S 的下标0pos S0 != S1,S1 != S2,所以S1 != T0,S2 != T0. 还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况啊。假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S2和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和T0 间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S2和T2时，发现不等，就去看next2的值，next2=0，意思是S2已经和T2比较过了，不相等，接下来去比较S2和T0吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来去比较S5和T2吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值nextn呢？（本文中next值、模式函数值、模式值是一个意思。）三. 怎么求串的模式值nextn定义：（1）next0= -1意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但Tk=Tj）（1kj）。如：T=”abCabCad” 则 next6=-1，因T3=T6 （3）nextj=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且Tj != Tk （1kj）。 即T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1 且Tj != Tk.（1kj）;(4) nextj=0 意义：除（1）（2）（3）的其他情况。举例：01）求T=“abcac”的模式函数的值。 next0= -1根据（1） next1=0 根据 (4) 因（3）有1=kj;不能说，j=1,Tj-1=T0 next2=0 根据 (4) 因（3）有1=kj;（T0=a）!=（T1=b） next3= -1根据 (2) next4=1 根据 (3)T0=T3 且 T1=T4 即 下标01234Tabcacnext-100-11若T=“abcab”将是这样：下标01234Tabcabnext-100-10为什么T0=T3,还会有next4=0呢, 因为T1=T4, 根据 (3)” 且Tj != Tk”被划入（4）。02）来个复杂点的，求T=”ababcaabc” 的模式函数的值。next0= -1 根据（1） next1=0 根据(4) next2=-1 根据 (2)next3=0 根据 (3) 虽T0=T2 但T1=T3 被划入（4）next4=2 根据 (3) T0T1=T2T3 且T2 !=T4next5=-1根据 (2)next6=1 根据 (3) T0=T5 且T1!=T6next7=0 根据 (3) 虽T0=T6 但T1=T7 被划入（4）next8=2 根据 (3) T0T1=T6T7 且T2 !=T8即下标012345678Tababcaabcnext-10-102-1102只要理解了next3=0，而不是=1，next6=1，而不是= -1，next8=2，而不是= 0，其他的好象都容易理解。03) 来个特殊的，求 T=”abCabCad” 的模式函数的值。下标01234567TabCabCadnext-100-100-14 next5= 0根据 (3) 虽T0T1=T3T4,但T2=T5 next6= -1根据 (2) 虽前面有abC=abC,但T3=T6next7=4 根据 (3) 前面有abCa=abCa,且 T4!=T7如果你觉得有点懂了，那么练习：求T=”AAAAAAAAAAB” 的模式函数值，并用后面的求模式函数值函数验证。意义：next 函数值究竟是什么含义，前面说过一些，这里总结。设在字符串S中查找模式串T，若Sm!=Tn,那么，取Tn的模式函数值nextn,1. nextn= -1 表示Sm和T0间接比较过了，不相等，下一次比较 Sm+1 和T02. nextn=0 表示比较过程中产生了不相等，下一次比较 Sm 和T0。3. nextn