KMP算法

注明：参考文献《信息学奥赛一本通》

———————————————————————————————————————“my name is the porter of nature”

介绍

KMP算法是用于字符串匹配问题的，它利用一种巧妙而又不失逻辑的方法去减少算法的时间复杂度，在处

理较多数据匹配时或者数据范围大的时候用处极大（反正我是五体投地），也就是如果问主串是否包含子

串的问题可以大幅度让你开心得飞起…

举个栗子 ：我们有一个主串— A=”aaaaaaaaaaaaaaaaab” 和 子串— B=“aaab”，如果我们要找从A串中哪

一个位置起开始匹配，通常是枚举位置后验证匹配，那么它的时间复杂度为O(n*m)[n为A串长，b为B串长]

,最坏情况下这通常不能接受，大大的TLE就给你奉上；而KMP算法即使是最坏情况，它也可以满足O(n)的

时间复杂度。

概念

首先我们明确几个概念。。。

A=”aaaaaaaaaaaaaaaaab”    B=“aaab”

~主串(母串)——即等待匹配的A串

~模式串——即用来匹配的B串

流程

假设我们现在有一个主串A=“abababaabab”和一个模式串B=“ababacb”，我们用实例去表示这个过程：

我们现在匹配到i=j=5时，此时前面的都可以匹配，但是A[6]!=B[6].

i= 1 2 3 4 5 6 7 8 9 …

    a b a b a b a a b a b …          (主串）

    a b a b a c b                          (模式串）

j= 1 2 3 4 5 6 7

于是我们就用你聪明的小脑瓜子想一下，我们现在应该将j改成更小的j’,使得j‘前面的字母可以满足刚好

和A串前面的匹配，然后继续匹配下去。这个时候我们可以发现，B串中前面j’个字母和末尾的j‘个字母

要完全相同，这样才能移动B串，如下面所示：

i= 1 2 3 4 5 6 7 8 9 …

    a b a b a b a a b a b …          (主串）

          a b a b a c b                    (模式串）

j=       1 2 3 4 5 6 7

这样的话我们就可让A[6]=B[4]了，即可以继续匹配下去。我们也可以得知，新的j的取值与i是没有关系

的，它就是一个B串起点在疯狂跳跃的过程，逆向思考的话，就是在前面的j对应的字母不能匹配的话，

就缩小j，使得B串能够跳跃去继续匹配罢了,,

那么我们可以预处理一个数组P[j]去处理，即它表示B组与A组匹配到B组第j个字母，第j+1个字母不能

匹配时，新的j最大可以是多少。则P[j]满足B[1……k] = B[j-k+1……j]。(好好消化一下再继续看）

此时我们继续匹配下去，则有：

i= 1 2 3 4 5 6 7 8 9 …

    a b a b a b a a b a b …          (主串）

          a b a b a c b                    (模式串）

j=       1 2 3 4 5 6 7

这时又出现A[7+1]!=B[5+1],我们就让B开始跳起来，因为新的 j = P[5] = 3；(P的求法后续再讲）

i= 1 2 3 4 5 6 7 8 9 …

    a b a b a b a a b a b …          (主串）

                a b a b a c b              (模式串）

j=             1 2 3 4 5 6 7

 但是a != b ,所以我们 继续 j = P[3] = 1;

i= 1 2 3 4 5 6 7 8 9 …

    a b a b a b a a b a b …          (主串）

                      a b a b a c b       (模式串）

j=                   1 2 3 4 5 6 7

依旧是不满足，那就 j = P[1] = 0了，它已经没力气了~~

i= 1 2 3 4 5 6 7 8 9 …

    a b a b a b a a b a b …          (主串）

                         a b a b a c b     (模式串）

j=                   0 1 2 3 4 5 6 7

所以我们只有j==m的时候，我们才可以匹配完全…但也存在后续匹配不了滴~

先打这个匹配过程的代码？

//实际操作中字符串数组以0开头，所以上面从1开始是指从第1个位置开始
j=0; 
for(i=0；i<sA.length();i++){
    while(j>0 && sB[j+1]!=sA[i+1]) j=P[j];
    //即不能继续匹配下去，且还没到没力气的时候，就继续减小j
    if(sB[j+1]==sA[i+1]) j++; 
    //此时可以继续匹配，那就匹配下去
    if(j==m) {
    printf("%ld ",i+1-m+1);// 子串在母串的位置 ，当然是第几个位置喽
    j=p[j];   //开启新征程
    }
}