题解 P3375 【【模板】KMP字符串匹配】

KMP算法主要用于字符串匹配，但是其扩展能解决很多字符串问题。下面我来给大家讲解KMP算法 tips:以下数组均为从0开始 ## 1、next数组 next数组的定义是对于一个字符串str,next[i]表示的是在str中 [0,next[i])以及 [i-next[i],i) 这两个区间中的字符严格相等的最大next[i]值(区间不能重叠 举个例子 `a b c a b c b b a b c` `0 0 0 1 2 3 0 0 1 2 3` `[a] b c [a] `=> `next[4]` = `1` `[a] [b] c [a] [b]` => `next[5]` = `2` `[a] [b] [c] [a] [b] [c]` => `next[6]`=`3` 画一张图意会  其中的线表示相同的一堆相同的字符,长方形指一个(一堆)字符,中间的省略号省略了一堆字符 手算不难得出，我们先不讲这个数组通过算法怎么生成的，我们先讲怎么用这个数组 ## 2、KM 在介绍普通的KM算法前我们先回顾一下解决字符串查找的朴素算法 ```cpp char s1[MAXN],s2[MAXN];//s1.find(s2); int l1=strlen(s1),l2=strlen(s2); int j=0,i=0; while (i!=l1){ if (s1[i]==s2[j]) i++,j++;//匹配 else i-=j-1,j=0;//失配 if (j==l2){ cout << i-j+1 << endl; j=0;//相当于失配 } } ``` 明显失配时的移动可以优化,那怎么优化呢,我们就要用到`next[]` 根据`next[]`我们可以画一张关于失配图  最佳的移动是这样  所以检测到失配时 `i`可以保留，`j` = `next[j-1]` 但是`j`肯定有等于`0`的情况,`j` - `1` 不就越界了吗? -我们就在计算时加一个F()函数检测`j` - `1`是不是越界了 于是用`next[]`优化后的代码就出来了 ``` #define F(x,nxt) (x<0?-1:nxt[x]) int i=0,j=0; while (i!=l1){ if (j==-1||s1[i]==s2[j]) i++,j++; else j=F(j-1,nxt); if (j==l2){ cout << i-j+1 << endl; j=F(j-1,nxt); } } ``` ## next[]的计算 考虑以下字符串,我们要算出它的`next[]` a b c a b c a b 手算得 0 0 0 1 2 3 1 2 显然对于每一个`next[i]`一种情况可以这么弄 `next[i]` = `next[i-1]` + `1` **if** `str[i]`==`str[next[i-1]]` 那当`str[i]`!=`str[next[i-1]]`的情况呢 先给一个结论,然后我们来试着证明它 我们就令`j` = `next[i-1]` ```cpp while (1){ if (str[i]==str[j]) {next[i] = j + 1;break;} //① if (str[i]!=str[j]) j = next[j] - 1; //② } ``` 即 `next[i]` = `j` + `1`,`str[i]`==`str[j]` ① `j` = `next[j]` - `1`,`str[i]`!=`str[j]` ② 一旦执行到①,`next[i]`就算完了 证明过程我们用一张图来意会  我们要求箭头指向的那个字符的next值,这里我们假设前面字符的next值已经求完了 但是我们可能会检测到②这种情况,图就变成了这样  这样的话显然是正确的,剩下的证明过程,提一个主要思路 1、证明真正的next值<算出来的值是假的 2、证明真正的next值>算出来的值是假的 又在上一章讲到我们还要把next[]往后移一位且next[0]=-1 怼在一起有代码 ```cpp #include<bits/stdc++.h> #define F(x,nxt) (x<0?-1:nxt[x]) using namespace std; char s2[1000010],s1[1000010]; int nxt[1000010]; int main(){ scanf("%s%s",s1,s2); int l1=strlen(s1),l2=strlen(s2); //计算nxt[] nxt[0]=0; for (int i=1;i<l2;i++){ int j=nxt[i-1]; while (j&&s2[i]!=s2[j]) j=nxt[j-1]; if (s2[j]==s2[i]) nxt[i]=j+1; else nxt[i]=0; } //匹配 int i=0,j=0; while (i!=l1){ if (j==-1||s1[i]==s2[j]) i++,j++; else j=F(j-1,nxt); if (j==l2){ cout << i-j+1 << endl; j=F(j-1,nxt); } } for(int i=0;i<l2;i++) cout << nxt[i] << ' '; return 0; } ```