KMP算法详解

---

详解：https://www.cnblogs.com/yjiyjige/p/3263858.html
https://blog.csdn.net/lee18254290736/article/details/77278769

字符串匹配的暴力方法与KMP的比较：

遇到以下情况时：

image.png

1. 暴力方法把匹配的指针下移一位

   
   image.png

2. KMP根据next数组跳过不需要遍历的部分：

   
   image.png

---

KMP的思想：

利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。

推理：

当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]

PS:为什么是i-k~i-1而不是i-k~i-x(x>1)？

因为如果是i-k~i-x的话说明就算j移到i-k还是无法匹配i-x~i-1这段字符串，所以必须以i-k开头i-1结尾。

image.png

---

next数组的含义：

当j位失配时，j需要回退到的地方，即next[j]。（j是pattern对应的指针）

next数组如何定义？又如何判断要跳过多少元素呢？

Next[0]==Next[1]== -1是默认值，但是在处理中第一位pattern[0]不匹配时要i++，其他只需要j=0即可。如果pattern[i]不匹配，则将j指针指向Next[i]=2，即j=Next[]；

---

Next数组的写法：

// 当第n位不匹配时怎么跳。
void getnext(char pattern[]){
  int i=0,j=0,k=0;
  // 事先约定好的两位
  Next[0]=-1;
  // 第一位不跳，-1位不存在匹配的情况。
  Next[1]=-1;
  // 第二位不匹配，但第一位匹配，移动一位。比如ab与ac不匹配，肯定将i移动到b后面。

  for(i=2;i<strlen(pattern);i++){
    // 从pattern[2]开始不匹配时
    Next[i]=-1;
    for(j=i-2;j>=0;j--){
      // j的结束位置从[0,i-2]，开始位置默认0的贴前字符串
      for(k=0;k<=j;k++){
        // [0,i-2]的贴后字符串
        //cout<<"i:"<<i<<"  k:"<<k<<"  "<<pattern[k]<<"  j:"<<j<<"  "<<pattern[i-1-j+k]<<endl;
        if(pattern[k]==pattern[i-1-j+k]){

        }
        else{
          break;
        }
      }
      if(k==j+1){
        Next[i]=j+1;
        // 最长的匹配子串长度(0-j),所以长度是j+1
        break;
      }
    }
  }
}

image.png

在k的循环体里面：

image.png

---

Next数组基础上的kmp:

void kmp(char text[],char pattern[]){
  int i=0,j=0;
  int t=strlen(text);
  int p=strlen(pattern);
  bool pass=false;
  while(i<t){
    // 只要看text的指针有没有越界即可，反正pattern的指针j越界就会跳出循环匹配成功
    //cout<<i<<"   "<<j<<"  "<<Next[j]<<endl;
    if(text[i]==pattern[j]){
      i++;
      j++;
    }
    else{
      if(Next[j]==-1&&j==0){
        // 如果没有找到串内重复的串，只需要将pattern的指针指向开头就好。
        // ab与ac如果把j=0，会陷入死循环。
        i++;
      }
      else if(Next[j]==-1){
        j=0;
      }
      else{
        // 如果匹配失败，将j指针指向Next[j]对应的地址。
        j=(Next[j]);
      }
    }
    if(j==strlen(pattern)){
      pass=true;
      cout<<"\nmatch: ["<<i-strlen(pattern)<<","<<i-1<<"]"<<endl;
      show(text,i-strlen(pattern),i-1);
    }
  }
  if(!pass)cout<<"\nNo matching"<<endl;
}