KMP算法总结

ps:蒟蒻写的不太好，推荐神犇写的一篇有关KMP的博客，非常清楚，有动图匹配全过程，看一遍就懂，戳我。
说明

• 本篇博客中的字符串都是从1开始的，后面不再解释。
  用途
• KMP算法主要用于快速字符串匹配的，假设我们要在是字符串\(s1\)中找一个子串\(s2\)，朴素的字符串匹配是枚举\(s2\)在\(s1\)中的位置，然后一个个比较，直到出现不同或者全部匹配为止，这个时间复杂度最坏是\(n^2\)的，效率太低，于是，就有了KMP,可以线性时间复杂度匹配子串。
  一些概念
• 对于一个字符串\(s\)，我们用\(f[i]\)记录这个子串前\(i\)个字符的最长的前缀和后缀相同的长度。(前缀不包括最后一个字符，后缀不包括第一个字符)
  例如对于字符串\(ababa\)
  第一个字符为\(a\),所以最长的前缀和后缀相同的长度为0，即\(f[1]=0\),
  前两个字符为\(ab\),\(f[2]=0\),
  前两个字符为\(aba\),最长前缀和后缀为\(a\),(不是\(aba\)),所以\(f[3]=1\),
  前两个字符为\(abab\),最长前缀和后缀为\(ab\),所以\(f[4]=2\),
  前两个字符为\(ababa\),最长前缀和后缀为\(aba\),(不是\(ababa\)),所以\(f[5]=3\),
  其实这个例子不够经典，不具有代表性,但也应该解释清楚了。
  基本思想

• 对于朴素的匹配算法，我们会发现，在匹配过程中，一但出现不匹配的字符，我们前面的匹配信息就全部舍弃，这样浪费了大量的时间，但是这个信息是可以利用起来的。假设我们在\(s1\)中匹配到了第\(i\)位，在\(s2\)中已经匹配了\(j\)位，第\(i\)于第\(j\)位是不匹配的，那么我们会发现\(s2\)的前\(j-1\)个字符的最长前缀和最长后缀就已经匹配了，也就是前面的\(f[j-1]\)位就已经匹配了,也就是\(s1\)的第\(i-f[j-1]\)到第\(i-1\)位与\(s2\)的第\(1\)到\(f[j-1]\)位已经匹配了,此时我们只需要把\(j\)修改为\(f[j-1]+1\)就可以继续匹配了，而每当\(j=m且a[i]=b[j]\)时，就是一次成功匹配。
  注意特判\(j=1\)且\(a[i]\ne b[j]\)时应该直接将\(i\)往后移一位。
  由于\(s1\)的每一个字符最多被访问一次,所以匹配的时间复杂度为O(n).

  for(int i=1,j=1;i<=n;++i,++j){
      if(a[i]!=b[j]){if(j!=1)j=f[j-1],--i;else j--;continue;}
      if(j==m)printf("%d\n",i-j+1),j=f[m];
  }

  \(f\)数组的预处理

• 匹配已经讲完了，现在我们要做的就是先预处理\(f\)数组了。
  这个其实就是不断的用串\(s2\)自己匹配自己。具体是怎样呢?直接看吧,手玩一下。

  for(int i=2;i<=m;++i){
      int j=i-1;
      while(b[f[j]+1]!=b[i]&&j>0)j=f[j];
      if(b[f[j]+1]==b[i])f[i]=f[j]+1;
      else f[i]=0;
  }

  整个KMP算法就这么多，非常好写，不过一般不会单独使用。
  完整代码(题目来源洛谷P3375【模板】KMP字符串匹配)

• “`

  include<bits/stdc++.h>

  using namespace std;
  const int N=1e6+20;
  char a[N],b[N];
  int f[N];
  int main(){
  scanf(“%s%s”,a+1,b+1);
  int n=strlen(a+1);
  int m=strlen(b+1);
  for(int i=2;i<=m;++i){
  int j=i-1;
  while(b[f[j]+1]!=b[i]&&j>0)j=f[j];
  if(b[f[j]+1]==b[i])f[i]=f[j]+1;
  else f[i]=0;
  }
  for(int i=1,j=1;i<=n;++i,++j){
  if(a[i]!=b[j]){if(j!=1)j=f[j-1],–i;else j–;continue;}
  if(j==m)printf(“%d\n”,i-j+1),j=f[m];
  }
  for(int i=1;i<=m;++i){
  printf(“%d “,f[i]);
  }
  cout<<endl;
  return 0;
  }

“`