[编程笔记]-KMP

前言

KMP真的很不好理解，但其实理解了原理，代码就没有任何的问题了。

原理

总概

KMP嘛，其实就是优化字符串匹配的过程。

优化的终点就是当前点匹配不上时的操作。对比如下：

• 暴力算法：后移一位，从头开始匹配。
• KMP算法：找到匹配串中距离当前点最近的可以与被匹配串匹配的点，直到当前点可以匹配为止。

（这句话可能有点绕，但学完整个算法就理解了。）

（至于为什么把它分在数据结构……你就说next数组存没存数据吧）

流程

整个KMP算法其实分为两步：

1. 找next数组
2. 匹配！

至于具体怎么做，马上就知道了。

实现

找next数组

原理

next数组，其实就是寻找如果当前点匹配不上，上一个最近的可以匹配的点。重点，就在于如何判断可以匹配。

假设被匹配字符串到了第i个元素，匹配字符串到了第j个元素，那么可以肯定的是，两个字符串当前元素前面的元素，一定是完全相等的。不然就没法匹配当前元素了~

• 如果当前元素相同，那最好，i和j各自前进一位，把刚才进行匹配的元素加入前面已经完成匹配的部分中。
• 如果当前元素不同，那就到了next数组发挥作用的时候了。

将两个字符串中已经匹配好的子串单独拿出来（包括被匹配串中移出的部分），可以看出，被匹配串的后缀，与匹配串是完全相同的。

之所以这样，是因为在匹配的过程中，匹配串肯定是从前往后进行匹配的，因此它的前缀必须先完成匹配。在这个匹配过程中，匹配串肯定是在向后移动，那么被匹配串中肯定就有元素匹配不上，那么这些元素就全都排在当前完成匹配的元素的前面，所以当前被匹配串子串的后缀肯定是完成匹配了的。

（这里不是说被匹配串整个串，只是当前对比元素的前面形成的完成匹配的子串）

所以可以得出，前缀与被匹配串的后缀相同的匹配串可以进行匹配。

那么上一个可以进行匹配的元素，肯定也满足这个性质。

当前的子串与被匹配串后缀相等，但是后一个元素无法匹配，就需要找到上一个在匹配串中满足条件的子串，用它的后一位元素再与被匹配串中当前匹配元素匹配。

所以新的元素的前缀也要与被匹配串的后缀相同。

而被匹配串的当前的最大相同后缀，其实就是匹配串当前已经完成匹配的子串。

后缀的后缀和前缀的前缀一定相同。

所以也就是要找到匹配串前缀中最长的前缀，与被匹配串后缀中最长的后缀相同。

联立第二句话与第四句话，当前最长的满足条件的子串就是当前匹配串子串中最大公共前后缀。

所以下一个匹配的元素就是最大公共前缀的后一位。也就是next数组中的存储的东西了。

归根结底，找next数组的过程，其实就是不断找最大公共前后缀的过程。

找的是当前匹配元素之前形成的子串中的最大前缀的后一位元素。

操作

现在问题就变成了找当前元素之前的子串（不包括当前元素）的最长公共前后缀大小的问题。

假设已经完成了第i个元素，它的next是j。
（相当于从第1个元素到第i-1个元素形成的子串中，最长公共前后缀长度是j-1）

现在，我们就对比元素i与元素j。

• 如果相同，那么next[i+1]=j+1，因为后缀新加入了一个与前缀新加入的元素相同的元素，还是最长公共前后缀，长度增加了一。最后j++, i++就行了。
• 如果不同，也就相当于两个字符串匹配的过程，j不断地去找上一个满足条件的元素j=next[j]，直到当前元素j与元素i相同为止，next[i+1]=j+1，然后j++, i++。
• 如果所有元素都不同，特计next[i+1]=0，表示无法匹配，后移一位重启匹配。

然后一直循环，直到整个匹配串找完为止。

匹配

怎么匹配？其实就跟找next数组一模一样，不过并不是对比同一个字符串的前后缀，而是匹配匹配串的前缀和被匹配串的后缀罢了。

思路其实是完全相同的。当匹配串完成了最后一个元素的匹配时，就说明整个串都完成匹配了。

代码

AcWing831-KMP字符串

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,M=1e6+6;

int n,m;
char p[N],s[M];
int ne[N];

int main(){
    cin>>n>>p+1>>m>>s+1;
    int i=1,j=0;
    while(i<=n){
        if(j==0||p[i]==p[j]) ne[++i]=++j;
        else j=ne[j];
    }
    i=j=1;
    while(i<=m){
        if(j==0||s[i]==p[j]) i++,j++;
        else j=ne[j];
        if(j==n+1){
            cout<<i-n-1<<" ";
            j=ne[j];
        }
    }
    return 0;
}

完结撒花o(￣︶￣)o

愉快地亖了