KMP算法浅析

KMP算法简介

  KMP算法是有Knuth、Morris、Ptatt三人合作的结果,并使用三人名字的首字母作为该算法的命名,该算法在匹配之前对模式串进行了分析,找出模式串的规律,由此大大提高了每次匹配失败后后移算法的性能,讲模式串匹配的时间复杂度提升到了O(n+m)级别。
  对于模式串的分析,需要求出模式串的next数组,next[j]表示了,如果当前位匹配不成功时,模式串的指针需要跳转到的位置,其计算方法和表示含义如下所示:

  由以上规则,可以很容易写出一个pattern字符串的next数组,如下示例所示:

pattern a b a a b c
j 0 1 2 3 4 5
next -1 0 0 1 1 2

  注意:这里我们字符串的下标都从0开始。

next数组的求解方法

  next数组的求解,可以使用定义的方法进行手动求解。但是算法的实现,则可以通过前一个位置的next数组的值推算出来,这种方法的证明不在此处给出,近给出算法的代码实现:

void GetNext(const string &pattern,vector<int> &nextofpattern){     //获取next数组
    int sizeofpattern=pattern.size();
    nextofpattern.resize(sizeofpattern);                            //初始化next数组的空间大小
    nextofpattern[0]=-1;                                            //next[0]为-1
    int i=0,j=-1;                                                   //初始化i和j,通过i遍历以计算每个位置的next数值,其中每次通过i的当前信息,推算i+1位置的next值,所以循环到下标size-2处
    while(i<sizeofpattern-1){                                       //j表示了一个最长相同前后缀的长度,
        if(j==-1||pattern[i]==pattern[j]){                          //如果j已经到达边界,即需要从模式串的头开始匹配(最长相同前后缀长度为0),则此处的next值为0,即要回到模式串的0号位
            ++i;++j;
            nextofpattern[i]=j;                                     //根据当前位置i推算下一个位置(i+1)的next值,如果当前位置i存在更长相同前后缀,则下一个位置(i+1)失配时
        }                                                           //回到模式串当前最长前后缀的下一个位置(由于下标从0开始,所以下一个位置就是最长前缀的长度)即j+1
        else j=nextofpattern[j];                                    //如果当前位置i无法在next[i]的基础上增长最长前后缀,则j缩短一些
    }

}

KMP算法的实现

  有了next数组之后,则可以使用KMP算法进行匹配,KMP算法的思想是:如果当前位匹配,则文本串和模式串的指针同时后移;如果当前位不匹配,文本串指针不动,匹配串的指针移动到next[j]的位置,继续匹配;直至模式串指针走完匹配完成或者文本串指针走完未完成匹配。其算法的代码实现如下:

int KMP(const string &str,const string &pattern,int pos){           //KMP算法,str为主串,pattern为模式串,pos为查找的起始位置。
    vector<int> next;
    GetNext(pattern,next);                                          //计算next数组
    int i=pos,j=0;                                                  //i为查找的起始位置,j为模式串的指针,初始化为0
    int sizeofstr=str.size(),sizeofpattern=pattern.size();
    while(i<sizeofstr&&j<sizeofpattern){                            //当没有匹配完时
        if(j==-1||str[i]==pattern[j]){                              //如果j=-1表示必须从头开始匹配(刚好j+1变成0,i+1从下一个新的主串位置开始),或者当前位置匹配时,指针都加一
            ++i;++j;
        }
        else j=next[j];                                             //失配时j指针回溯
    }
    if(j==sizeofpattern) return i-sizeofpattern;                    //找到时返回模式串出现的起始位置
    else return -1;                                                 //否则返回-1表示为找到
}

KMP算法测试

  我们调用KMP算法对其实现进行测试,并检查求解next数组的函数是否工作正常,添加相应的头文件之后,使用以下的代码进行测试:

#include<bits/stdc++.h>
using namespace std;
void GetNext(const string &pattern,vector<int> &nextofpattern);
int KMP(const string &str,const string &pattern,int pos);
int main(void){
    string test="abaabc";                                           //测试模式串
    vector<int> next;
    GetNext(test,next); 
    for(int i=0;i<next.size();i++){                                 //输出next数组
        if(i) putchar(' ');
        cout<<next[i];
    }
    cout<<endl;
    string str="aaaabaaabaabaabcaabac";                             //KMP匹配测试
    cout<<"Pos of "<<test<<" in the string "<<str<<" is "<<KMP(str,test,0);
    return 0;
}

//补充上Getnext和KMP的代码实现

  最终的输出如下:

-1 0 0 1 1 2
Pos of abaabc in the string aaaabaaabaabaabcaabac is 10

手动求解next数组

  对于一串字符,我们先对每个位置求解出其最长相同前后缀长度,但是不能等于整个串的长度,然后将求解到的序列右移一位,0号位补上-1便是下标从0开始的next数组,然后在此基础上每一个数字都加一,获得下标从1开始的next数组。
  示例如下:模式串abaabc

//每个位置的最长前后缀长度
a           0
ab          0
aba         1
abaa        1
abaab       2
abaabc      0
//得到一组序列
0 0 1 1 2 0

  序列右移一位,0号位补-1得到下标从0开始的next数组:

-1 0 0 1 1 2

  上述序列每一个数字都加一,得到下标从1开始的next数组:

0 1 1 2 2 3

当珍惜每一片时光~