KMP算法通俗详解（新手向）

一、暴力子字符串查找算法

解释KMP算法之前，需要先回顾一下普通暴力算法的工作流程：

#ifndef FORCE_H
#define FORCE_H
#include<string>
int find(const std::string &txt, const std::string &pat) {
    if (pat.empty() || txt.empty()) return -1;
    for (int i = 0; i <= txt.size() - pat.size(); i++) {
        int j = 0;
        while (j < pat.size() && txt[i + j] == pat[j]) 
            j++;
        if (j == pat.size()) return i; 
    }
    return -1; 
}
#endif

首先枚举匹配位置，对于每一个位置，递增j指针以检查之后的字符是否完全匹配，如果发现有不匹配，就尝试下一个起始位置。

暴力子字符串查找算法的时间复杂度为$O(nm)$，数据量较大时效率较低。可以观察到暴力算法每次匹配失败时都要回到原来位置，把模式串反复的一位一位往后挪，如果文本开头有很大一串和模式串相似但无法匹配的字段，就会在这块浪费很长的时间。

KMP算法的改进思路很简单，就是当匹配失败时，不仅仅把模式串往后移一位，而是挪动很多位，这样可以避免掉无用的比较操作。

那么匹配失败时具体要往后挪多少位呢？

当i=1，模式串匹配失败时，观察一下前面匹配成功的部分，可以很轻易发现，两个绿框圈起来的部分是完全一致的！

既然这两部分在之前的匹配过程中已经被完全匹配，那么可以直接将前一段的开头和原来后一段的开头对齐，从而避免了再一位一位往后挪，可以直接跳过中间i=2时的匹配步骤。

二、前缀函数

定义一个字符串$s$的border为一个不为的$s$子串$s\prime$，满足$s\prime$既是$s$的真前缀，又是$s$的真后缀。回顾上文的轨迹图，可以观察到aba实际上就是ababa的border，那么在匹配失败时只需要预先知晓模式串从0到j-1的子串的最长border长度，并按照其重置i指向的位置即可。

将模式串从0到j-1的子串的最长border长度表示为$b_j$， 即前缀函数。先贴出前缀函数的计算代码：

int lo=0,b[1000010];
for(int hi=1;hi<pat.size();hi++){ 
  while(lo>0 && pat[lo]!=pat[hi])
    lo=b[lo-1];
  if(pat[lo]==pat[hi]) lo++;
  b[hi]=lo;
}

lo代表最长border的长度，从1开始枚举hi（如果hi是0的话根本没有任何border吧），每次枚举时判断lo和hi指向的字符是否相等，如果是，那么lo自增；如果否，那么lo一直自减，直到lo和hi的字符相等或者lo没法再减了。最后把$b_{hi}$的值设为lo。

这样做看似难懂，实则有据可寻，只是新学起来难以弄清逻辑，自己试着画一遍轨迹图就可以理解了～

三、KMP子字符串查找算法

有了上面的知识储备，实现kmp就易如反掌了：首先计算出模式串每一前缀的最长border长度，然后进行匹配，匹配失败时按照b数组的内容重设模式串位置即可。

注意这里有一个大坑：重设模式串位置后不需要再从模式串的第一位开始匹配！既然已经按照border移动了模式串，那么开头那几位肯定是相等的，没有必要再来重新匹配了。因此我们使用指针i代表当前应该比较的文本位置，指针j代表应该比较的模式串位置，代码实现如下：

#ifndef KMP_H
#define KMP_H
#include<string>
using namespace std;
int find(const string &txt,const string &pat){
  if(txt.size()<pat.size()) return -1;
  int lo=0,b[1000010]={0};
  //计算b数组
  for(int hi=1;hi<pat.size();hi++){
    while(lo>0 && pat[lo]!=pat[hi])
      lo=b[lo-1];
    if(pat[lo]==pat[hi]) lo++;
    b[hi]=lo;
  }
  //开始匹配
  for(int i=0,j=0;i<txt.size();i++){
    while(j>0 && txt[i]!=pat[j]) //失配 回退j
      j=b[j-1];
    if(txt[i]==pat[j]) //匹配
      j++;
    if(j==pat.size()){ //找到匹配
      return (i+1)-pat.size();
      //j=b[j-1];   ->除非你还想接着匹配
    }
  }
  return -1; //没有匹配
}
#endif