极简KMP小结

学习 / /
文章目录

要找abcabcabcd中是否含有abcabcd，有很多种办法，今天总结的是KMP算法。

本文为自我总结，建议先看其他文章思考一下。

KMP算法其实并不复杂，其核心原理就是用一个数组储存待匹配字符串中，对于其中每一个字符，这个字符前面有多少个字符和从头开始看是完全一样的数量。

举例子，如原串为abcabcabcd，待匹配串为abcabcd。其中d前面有abcabc，从头开始数的abc(第一二三个数)和d前面的abc(第四五六个数)是一样的，所以如果轮到d的时候不匹配了，那就直接从第四个数做比较即可，而不必从头开始再暴力匹配。

比如我们看匹配过程：

a b c a b c a b c d
a b c a b c d

轮到d时其与a不匹配，那么可以直接滑动到：

a b c a b c a b c d
a b c a b c d

计算这个数组的方法很简单：

int GetNext(SqString t,int next[])
    {
      int j = 0, k = -1; 
      //j作遍历，k记录t.data[j]之前与t开头相同的字符个数
      next[0] = -1; 
      //固定的，next第一个值为-1
      while(j < t.length -1)
      {
        if(k == -1 || t.data[j] == t.data[k])
        //k为-1或比较的字符串相同时
        {
          j++;k++;
          next[j] = k;
        }
        else k = next[k];//k回退
      }
    }

这个算法还可以改进，因为如果出现aabaaabaaabc中找aaabaaabc的情况：

a a b a a a b a a a b c
a a a

到第三个就不匹配，但是第二个和第三个都是“a”，所以第二个肯定也不匹配，改进算法如下，就是在里面加了个对重复字符情况的判断，遇到最坏情况（无重复）的时候复杂的与上面代码一样，但是遇到有重复的时候会快一些：

int GetNext(SqString t,int next[])
    {
      int j = 0, k = -1; 
      //j作遍历，k记录t.data[j]之前与t开头相同的字符个数
      next[0] = -1; //固定的，next第一个值为-1
      while(j < t.length -1)
      {
        if(k == -1 || t.data[j] == t.data[k])
        //k为-1或比较的字符串相同时
        {
          j++;k++;
          if(t.data[j] != t.data[k]) next[j] = k;
          //这里就加了个判断，不一样的话就next[j] = k
          else next[j] = next[k];
          //就多了这一行，面对一样的情况就直接赋next[k]的值
        }
        else k = next[k];//k回退
      }
    }

调用GetNext的kmp算法：

int KMP(SqString s,SqString t)
    {
      int GetNext[MaxSize] = 0, i = 0, j = 0;//i遍历原串，j遍历带匹配穿
      Next(t,next);//调用next函数
      while(i < s.length && j < t.length)
      { 
        if(j == -1 || s.data[i] == t.data[j]) {i++;j++;} 
        //若字符相等继续遍历
        else j = next[j];//不相等j回跳
      } 
      if(j >= t.length)
        return(i-t.length);
        //j遍历完，即为找到，返回位置
      else
        return (-1);//未找到，返回-1
    }

从头到尾彻底理解KMP

字符串匹配的KMP算法

--随缘箭·版权所有：极简KMP小结--