KMP算法

2021.12.16 by Ludwig

最近重新学习kmp算法，好像在大学乃至考研我都没闹明白kmp是咋回事，更不用说手撕，但也总觉得这要逃下去不是办法，花了两天时间，总算略微懂了点皮毛。网上的教程五花八门，next数组也各式各样。这篇不是教程也不是笔记，仅作为我个人的学习记录。

这篇博客代码和最后的图解使我对kmp的理解有很多帮助：https://www.zhihu.com/question/21923021 ,仅作为分享，此外还参考了王道书，学习了怎么手算nextval数组做考研题目，怎么用代码求解nextval数组。

最后运用kmp算法，完成了leetcode.28。

学习kmp意外的收获是，对参数传递一个数组，对指针的使用有了更深刻的理解，运用也更自如。

在期间踩了很重要的一个关于c++语法的坑，出现了一个使我百思不得其解的bug，以下为记录。

next数组

求解next数组，现在在我的理解下就是模式串先自身掐头去尾作匹配，next[0]恒为-1，代码如下：

void getNext(int* next,string s){
      next[0]=-1;
      int i=0;
      int j=-1;//想象两个模式串，串首差一位错开作模式匹配，以此得到最长相等前后缀大小
      while(i<s.size()){
          if(j==-1||s[i]==s[j]){
              i++;
              j++;
              next[i]=j;//理解一下为什么j=-1时是怎样操作的
              //如果j=-1，说明第一个位置没有匹配上，此时，i后移，由于++，j又变为0
          }else{
              j=next[j];//回退
          }
      }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

nextval数组

nextval数组是对next数组的优化。改动非常的小，但却很重要。

void getNextVal(int* nextval,string s){
      nextval[0]=-1;
      int i=0;
      int j=-1;
      while(i<s.size()){
          if(j==-1||s[i]==s[j]){
              i++;
              j++;
              /****************************/
              if(s[i]==s[j]){
                  nextval[i]=nextval[j];
            }else{
                  nextval[i]=j;
            }
              /****************************/
        }else{
              j=nextval[j];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

leetcode.28 实现 strStr()

class Solution {
public:
    void getNext(int* next,string s){
        next[0]=-1;
        int i=0;
        int j=-1;
        while(i<s.size()){
            if(j==-1||s[i]==s[j]){
                i++;
                j++;
                next[i]=j;
            }else{
                j=next[j];
            }
        }
    }
    int strStr(string haystack, string needle) {
        int next[needle.size()+1];
        int i=0;
        int j=0;
        getNext(next,needle);
        //注意这里while内不能写成`j<needle.size()`
        //因为j可能等于-1，见下文c++的坑
        int nSize=needle.size();
        while(i<haystack.size()&&j<nSize){
            if(j==-1||haystack[i]==needle[j]){
                i++;
                j++;
            }else{
                j=next[j];
            }
        }
        if(j==nSize){
            return i-j;
        }else{
            return -1;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

note: 主串指针i永远不回溯。

c++的坑

#include <string>
#include <iostream>
using namespace std;

int main(){
      string a="hello";
      cout<<"a.size()="<<a.size()<<endl;
      if((-1)<a.size()){
                cout<<"true"<<endl;
    }else{
          cout<<"false"<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

jaden@sunjuanxiongdeMacBook-Pro ~ %g++ test.cpp 
jaden@sunjuanxiongdeMacBook-Pro ~ %./a.out 
a.size()=5
false
jaden@sunjuanxiongdeMacBook-Pro ~ %
1
2
3
4
5

为什么会这样，-1明明小于a.size()，为什么打印结果是false？？

在c++中，诸如string、vector等类型的size()方法返回的是一个size_type类型的无符号整型!，如果在表达式中混和使用了带符号数和无符号数进行比较，将产生意想不到的结果。运算时-1会被当成无符号整型数处理，此时-1的二进制最高位为1是一个非常大的数，因此返回false。在进行判断size()时，还是应该使用0进行比较。或者用一个int型变量记录size()的值。

此处还可以写成 j+1<needle.size()+1, 这样也能规避错误。