KMP算法

KMP算法就是在一个大长的字符串里找小的字符串的算法。

// 字符串匹配之暴力法
int S[N],p[M];
for(int i = 1;i<=n;i++){ // 遍历从i开始的字符有没有可能匹配上
  bool flag = true;
  for(int j = i;j<=m;j++){
    if(S[i] != p[j]){
      flag = false;      // 已经出现没有匹配上的了
      break;
    }
  }  
}

KMP算法就是将j指针每次移动一个改变成每次移动最长公共子串个长度,这样就能极大的减少比较次数

#include <iostream>
using namespace std;
const int N = 10e5+10,M = 10e6+10;
char s[N],p[M];
int n,m;
int main(){
  cin >> n >> s+1 >> m >> p+1; // 输入的匹配串和模式串都是从下标为1开始输入，下标为0的单元等同于浪费了，不过无所谓
  
  // 求ne[]数组
  for(int i=2,j=0;i<=m;i++){
    while(j && s[i]!=p[j+1]) j = ne[j];
    if(j && s[i]!=p[j+1]) j++;
    ne[j] = j;
  }
  
  
  // KMP匹配
    for(int i = 1,j = 0;i<=n;i++){ // 遍历匹配串的每一个字母,j是输入串的指针
    // 匹配失败的情况
    while(j && s[i]!=p[j+1]) j = ne[j]; // j往回回溯
    // 匹配成功 
    if(j && s[i]!=p[j+1]) j++;
    
    if(j == m){  // 满足匹配条件后，打印开头下标
      printf("%d",i-m);
      j = ne[j];
    }
  }
  return 0;
}