软考-数据结构-KMP算法

KMP算法又称为改进的模式匹配算法，改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右滑动尽可能远的距离，再继续进行比较。

设模式串为p，主串S。在KMP算法中，依据模式串p的next函数值实现子串的滑动。令next[j]=k，当模式串中的pj与与主串S中的相应字符不相等时，滑动至pnext[j]与主串的相应字符进行比较。
next函数的定义如下：

例：

求模式串p “abcabac” 的 next，前两个字符固定对应-1和0，字符串下标从0开始。
字符下标：0 1 2 3 4 5 6
字符串 p： a b c a b a c
next 值 ： -1 0

第2个字符 ‘c’：前一个字符‘b’的next值为0，取p[0]='a’与‘b’作比较，不相等，由于next[0]=-1，结束。'c’的next值=next[0]+1=0

第3个字符 ’a‘：前一个字符‘c’的next值为0，p[0]='a’不等于c；next[0]=-1，结束。‘a’的next值为0

第4个字符’b‘：前一个字符’a’的next值为0，p[0]=‘a’=‘a’，即在前一个字符’a’的next值+1=1

第5个字符’a’：前一个字符’b’的next值为1，p[1]=‘b’=‘b’，即’a’的next值为前一个字符’b’的next值+1=2

第6个字符’c‘：前一个字符’a’的next值为2，p[2]=‘c’不等于’a’，取next[2]=0，即p[0]=’a‘=‘a’，'c’的next值为1
最后得到：
字符下标：0 1 2 3 4 5 6
字符串 p： a b c a b a c
next 值 ： -1 0 0 0 1 2 1

下面为KMP算法匹配过程：

例，设主串为’abacbcabababbcbc’，模式串为”abababb’模式串的next值如下，其中，i是主串字符的下标，j是模式串字符的下标。

下 标 j ： 0 1 2 3 4 5 6
字符串p：a b a b a b b
next [j] ：-1 0 0 1 2 3 4

第一趟匹配从S[0]与p[0]开始，直到S[3]不等于p[3]，结束第一次匹配；令j=next[3]=1，进行第二次匹配，S[3]不等于p[1]，结束第二次匹配；令j=next[1]=0，进行第三次匹配，S[3]不等于p[0]，结束匹配。此时可以看出，主串中从i=3开始的子串不可能与模式串相同，使i++，从S[4]与p[0]继续开始新一轮匹配过程…，直到某一趟匹配成功，或在主串中找不到模式串而失败。