KMP算法 （自己复习专用）

主要讲述kmp算法的模板以及重点掌握next数组的含义。（力扣28）

kmp算法其实是先自己跟自己匹配构造next数组，然后才是模板串与目标串的匹配

先讲述next数组的含义

next[i]=len表示前i个字符，前len个字符串和后len个字符串是相等的。且在所有满足前缀等于后缀的值中，len是最大的

这就是next数组的含义。

kmp算法下标最好从1开始。

int strStr(string s, string p) {
       if(p.empty()) return 0; //特判边界情况
       int n=s.size() ,m=p.size();
       s=' '+s,p=' '+p;  //最好下标从1开始
       vector<int>next(m+1) ;  //next 数组存储的是一个字符串前缀和后缀相等的最大长度
       for(int i=2,j=0;i<=m;i++)  //自己和自己匹配
       {
           while(j&&p[i]!=p[j+1]) j=next[j];  //这行的理解看下面
           if(p[i]==p[j+1]) j++;
           next[i]=j;
       }
       for(int i=1,j=0;i<=n;i++) //两个字符串匹配
       {
           while(j&&s[i]!=p[j+1]) j=next[j];
           if(s[i]==p[j+1]) j++;
           if(j==m) return i-m;
       }
       return -1;
    }

现在我们谈一下

while(j&&p[i]!=p[j+1]) j=next[j]; 

当枚举到p[j]跟s[i-1]相等的时候，我们接下来要判断p[j+1]跟s[i]是否相等。

如果p[i]!=p[j+1] ，说明不匹配，此时就要使j=next[j]，此时j变成[0-j]中最大的前缀==后缀的长度len，此时j=len,j表示的是在模板串中的下标。（注意j是匹配过程中模板串的下标）。

当不匹配的时候，需要后缀与前缀相等，同时还要让挪动的距离最小，所以就需要前缀和后缀相等的为最大长度，这就是next数组的含义。可以就完事了哈哈。主要是要记着next数组的含义，以及kmp的一些下标和边界的判断。

然后继续判断p[i]跟p[j+1]是否相等，如果相等，则j++，模板串位置后移一位

同时更新next[i]=j，next数组的含义一定要深记于心。这行代码并不是都用，只用于自己与自己匹配的时候。是用来构造next数组的。因为如果p[i]==p[j+1]时，此时原串到位置i，目标串j++后仍未j，next[i]=j，表示原串[0,i]前缀等于后缀的最大长度就是j这个数值啊。（注意kmp下标最好从1开始）

这篇博客，是为了自己之后复习，讲的云里雾里，不要观看。