本文共 727 字，大约阅读时间需要 2 分钟。

前言

虽然之前有用过，但是只是知道原理，求next数组的部分有点模糊。本篇详讲。

我的理解

说白了，KMP就是从暴力解法开始的。

#include
   
                   //暴力解法#include
    
     #include
     
      using namespace std;int main(){
       char a[100],b[100];    cin>>a>>b;    int i=0,j=0,blen=strlen(b),alen=strlen(a);    while(1){
           if(i==alen){
               cout<<-1<
     
    
   

显然，我们在匹配失败的那个位置之前的主串已经都匹配过了，已经与模式串建立联系了，我们只用把模式串的前后缀建立联系就行了。

#include
   
    #include
    
     #include
     
      using namespace std;int next[100];char b[100];void getnext(int len){
       int j=0,k=-1;    next[0]=-1;    while(j
      
       >a>>b;    int i=0,j=0,blen=strlen(b),alen=strlen(a);    getnext(blen);    while(1){
            //与暴力解法相类        if(i==alen){
               cout<<-1<
      
     
    
   

转载地址：http://iwuzi.baihongyu.com/