因为算法不好理解，所以记个笔记吧。

---

核心思想

KMP算法是用来做子串匹配的，可以用更小的时间复杂度找到一个字符串在另一个字符串中匹配的子串。

主要理解一个点就是找到next数组，并且理解为什么next数组是可行的。

以字符串s = "asdasddasdf", t = "asdf";为例子，我们需要找到这样一个数组，满足当s[i] != t[j]时，next[i]+1为j的下一次取值。

当字符串s中j+1的位置不等于i的位置时，j取next[j]的值，直到j<=0或者两个位置相等，而相等的时候，则j增加1。每次循环的过程让next[i] = j。

得到next数组的代码如下：

  void getNext(vector<int> &next,  const string &s){
      next[0] = -1;   //初始化第一个字符为-1
      int j = -1;     //初始化j为-1
      for(int i = 1; i < s.size(); i++){
          while(j > 0 && s[j+1] != s[i]){
              j = next[j];
          }
          if(s[j+1] == s[i]){   //当目标字符串中j+1的字符等于i时，意味着有重复字符，则使j增加
              j++;
          }
          next[i] = j;
      }
  }

我们有了next数组后，很容易就能在时间复杂度O(n)的情况下找到匹配的子串了：

  int main(){
      string s = "asdasddasdf";
      string t = "asdf";
      vector<int> next(s.size());
      getNext(next, s);
      int j = 0;
      for(int i = 0; i < s.size(); i++){
          if(s[i] == t[j]){
              j++;
              if(j == t.size()){
                  cout<<"ans:"<<i-j+1;    //输出第一次出现的子串
                  break;
                  //如果多次找到匹配子串位置，这里可以不跳出循环，并置j = 0;
              }
          } else {
              j = next[i]+1; //当字符不匹配的时候，j指针移动到next[i]+1的位置
          }
      }
      cout<<endl;
      return 0;
  }

我讲得很粗略，具体推公式，可以看这个作者的解释：

什么是KMP算法

« 操作系统进程线程