看了几天KMP算法，终于有眉目了！

 

KMP算法是一种改进的模式匹配算法，他到底和传统的模式匹配法有什么区别呢？

例如：

主串A：  a b a b c a b c

模式串B：a b c a c

传统的方法是先用i指向主串A中的第一个元素，j指向B中的的一个元素。若是对应A，B中的元素相同则i，j分别向后移，直到对应的A[ i ] < >B[ j ]，此时回溯指针i，j（i 向前进一步，j = 1）重新开始比较，知道B模式串完全凭匹配为止。

你会发现这样很麻烦，每次不相同的时候就要回溯。KMP算法就解决了这个问题。

如上例，比较到i = 5 ， j = 7 时：

              i = 7

   

a

b

a

b

c

a

b

c

a

c

  

A：

            j = 5

a

b

c

a

c

        B：

我们不必回溯指针，利用A[ 6 ] = B[ 1 ] = B[ 4 ]这个特点你可以直接将B串继续向前推进。

直接比较 B [1] 和 A [ 7]。说白了KMP算法就是解决失配时模式串向前推进多少步，即，失配后应与哪一个元素继续比较。上题中，失配前一个元素和第一个元素相同，也就是说，

当我们将B串向前推进3 个单元后直接比较第二个元素B[ 2 ]看是否与A[ 7 ]相同。也就是说当失配前有一个元素和第一个元素相同时我们可以直接比较模式串中的第二个元素。

现在推广到一般：

假设主串为'‘S1 S2 S3.......Sn’ ，模式串为‘P1 P2 P3 ........Pn’当比配过程中，若产生Si< > Pj ,且Pj前有k - 1个元素满足 ‘Pj - k + 1........Pj -1’ = ‘P1......Pk-1’（我们希望k是满足此条件的最大值，我的理解是最大限度的模仿上一次的匹配，也就是最大限度利用上次匹配的信息）；若有满足此条件的k - 1存在，下次我们就可以直接比较Si 和 Pk 了。我们可以用函数next[ j ] = k来表示失配后应继续比较的字符位置。综上可以定义next函数：

0   当j = 1时

next[ j ]  =  Max{ k | 1 <  k  < j且‘Pj - k + 1........Pj - 1’ = ‘P1......Pk-1’}

此集合不为空时

                    1    其他情况

第二个公式非常重要，意思再重复一遍：next[ j ] =  k,意味着在失配处j之前有k -1个元素和模式串最先的k - 1个字符相同。j 处失配我们就直接比较k处。根据next函数看书上的KMP算法不难理解。一直困扰我的是next函数的求法，给定一段模式串如何编程求出next函数呢？

书上说求next函数的问题把模式串既当模式串又当主串，书上还说可以用递推的方法来求next函数。怎么个递推呢？next [ 1 ] = 0不用说了。现在就是知道next[ j ]  =  k，怎么求next[j + 1]。next[ j ]  = k的意思我们强调过了：若产生Si< > Pj ,且Pj前有k - 1个元素满足 ‘Pj - k + 1........Pj - 1’ = ‘P1......Pk-1’（k 为满足条件的最大值）；如图示：

P1

.........

Pk - 1

Pk

.......

Pj - k +1

............

Pj -1

Pj

Pj +1

......

要求next [ j + 1]就有两种情况：

1， Pk = Pj 此时Pj + 1之前有k个元素满足和字符串之前的k个元素相同。所以

next [ j +1]  =  k + 1，也就是next[j + 1] = next[ j ] + 1; 

2， 现在看Pk< > Pj时，这个时候就应该想到模式匹配的问题书上说“求next函数的问题 把模式串既当模式串又当主串”这句话我们现在这样看,如图：

P1

.....

Pk - 1

Pk

......

Pj - k +1

....

Pj -1

Pj

Pj +1

......

P1

.......

Pk - 1

Pk

......

Pj - k +1

........

Pj -1

......

现在Pj < > Pk 根据之前所讲，next[ k ] 就应该是下一个和Pj比较的地方,假设next[ k ] = k',

Pk' = Pj此时next[j + 1] = k' + 1；若还此时仍然有Pk' < >Pj,也就是仍然失配，很明显我们必须继续找下一个可能存在Pn= Pj 的地方，当然还是用模式匹配的方法求next[ k ']直到存在

Pnext[ next[ next [ .....]  ] ] = Pj，此时next[j + 1] = next[ next[ next [ .....]  ] ]  + 1；如果不存在 next[ j + 1] = 1，意味着我们必须从第一个开始比较。综上描述可以写出求next函数的伪代码：

void  get_next (SString  T, int next [])

{

i = 1;next[ 1 ] = 0; j = 0;

while(i < T[ 0 ] )

{

if (j == 0 ||  T[ i] = T[ j ])

{i++; j++; next [ i] = j;}

else

j = next[j];

}

}

问题貌似已经解决了，其实不然，上面写的算法还有一个不足。例如模式串为a a a a b时。与主串 a a b a c a a,匹配一下。如图：

a

a

a

b

c

a

a

a

a

a

a

b

i = 4， j =4 时失配， 此时右移多少个单元呢？一眼就可以看出来要右移四个单位。

但是具体是怎么做的呢？我们发现此时Pj < > Si,并且Pj = Pk。所以应该直接跳到

P next [k] 处来比较，可是如果P next[ k ] = Pj 呢？我们当然要继续往下找P next[next[...]]

。若最后next[next[...]] = 0，找到第一个还是有P0 = Pj ，所以我们应该把主串中的指针往后移一位继续与P1比较。得到修正next函数的伪代码：

void get_nextval(SString T, int nextval[])

{

i = 1; nextval[ 1 ] = 0; j =0

if (i  < T[ 0 ])

{

while (j == 0 || T[i] == T[j])

{

  i ++;

j ++;

if (T[i]  ! =  T[j])

nextval[i] = j;

else  j =nextval[j];

}

}

}