极简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

GetNext的计算

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

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回退
      }
    }

GetNext的改进

这个算法还可以改进,因为如果出现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算法

发表评论

发表评论

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.

一片死寂