字符串的匹配值得是，在一个指定的字符串文本(长度为n)中找到某个字符串（模式串，长度为m）的出现的位置，简单匹配的方式，时间复杂度O(n*m)，在此基础上有改进的匹配算法KMP。

目录

KMP算法浅析

KMP算法简介

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

　　注意:这里我们字符串的下标都从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