KMP 字符串模式匹配详解

KMP 字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一 . 简单匹配算法 基本的模式匹配算法：以主串的某个字符与子串的第一个字符相比较，若相等，则继续比较二者的后一个字符，否则主串的字符指针从开始与子串第一个字符比较处后移一个位置，而子串的字符指针重新指向子串的第一个字符。 例如：在串S=”abcabcabdabba”中查找T=” abcabd”:先是比较S[1]和T[1]是否相等，然后比较S[2] 和T[2]是否相等…我们发现一直比较到S[6] 和T[6]才不等。如图：  当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图： 又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。返回T在S中的起始下标4。如图： 二 . KMP 匹配算法 KMP算法：KMP算法是对传统模式匹配算法的较大改进，在传统的模式匹配算法中，当出现主串中的字符与子串中的字符不等时，同时向前回溯了两个指针，一个是主串的指针，一个是子串的指针。而KMP算法的基本思路是在不回溯主串的指针，而只回溯子串的指针的情况下完成模式匹配，这样就省去了回溯主串指针进行比较的一部分时间。 KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。 还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[6] 和T[6]不等后，S下标不是回溯到2，T下标也不是回溯到开始，而是根据T中T[6]==’d’的模式函数值（next[6]=3，为什么？后面讲），直接比较S[6] 和T[3]是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。。。最终在S中找到了T。如图： next[6]=3含义： 其实这个3示T[6]==’d’的前面有2个字符和开始的两个字符相同”。请看图 ：因为，S[5] ==T[5]，S[4] ==T[4]，根据next[6]=3，有T[4]==T[1]，T[5] ==T[2]，所以S[4]==T[1]，S[5] ==T[2]（两对相当于间接比较过了），因此，接下来比较S[6] 和T[3]是否相等。。。 有人可能会问：S[4]和T[1]，S[5] 和T[2]是根据next[6]=3间接比较相等，那S[2]和T[1]，S[3] 和T[1]之间又是怎么跳过，可以不比较呢？因为S[1]=T[1]，S[2]=T[2]，S[3]=T[3]，而T[1] != T[2], T[2] != T[3],==> S[1] != S[2],S[2] != S[3],所以S[2] != T[1],S[3] != T[1]. 还是从理论上间接比较了。 三 . 怎么求串的模式值 next[n] 定义 ：           0   如果j=1 next[j]={ Max{k|1