KMP(MP)小记

Sweetlemon · 2018-10-17 21:45:36 · 个人记录

今天写了一遍\text{KMP}，看来也没有想象中那么难写嘛……

首先是\text{next}数组的求法。很多博客里说是“自匹配求\text{next}”，但是我完全不懂。直到看到了知乎上的这篇文章，才终于掌握了求\text{next}的方法。这个回答中的“次优”二字很妙，点破了求\text{next}的真谛。如何更好的理解和掌握 KMP 算法? - 逍遥行的回答 - 知乎

下面对\text{next}数组的求法给予简单说明。

本文中\text{next[i]}指的是\text{s[0...i]}这一段中，既是真前缀又是真后缀的最长子串的长度，如在字符串"aaaaa"中，\text{next[4]}=4。

我们假设现在已经求出了\text{next[0]}\sim\text{next[i-1]}，现在想求\text{next[i]}。
我们已知\text{s[0]}\sim \text{s[next[i-1]-1]}和\text{s[i-next[i-1]]}\sim \text{s[i-1]}这两段是一样的，如果\text{s[next[i-1]]}和\text{s[i]}也是一样的，那岂不是很好？如果是这样，\text{next[i]}便等于\text{next[i-1]+1}。
然而有时候（大多数时候）事情并没有这么简单。我们悲哀地发现\text{s[next[i-1]]} \neq \text{s[i]}。这时我们怎么去求\text{next[i]}呢？
我们经过思考可以发现，\text{s[0]}\sim \text{s[next[i]-2]}和\text{s[i-next[i]]}\sim \text{s[i-1]}这两段是一样的。那么，这两个公共的前缀及后缀应该也是\text{next[i-1]}的一个次优解。

我们经过探索知道，\text{next[i]}的次优解正是\text{next[next[i]]}。

因此，我们的方法是，设一个变量t，若\text{s[i]!=s[t]}且t>0，则使t不断等于\text{next[}t-1\text{]}。直到跳出循环条件，则把\text{next[i]}设为t+1或0。

求\text{next[i]}的代码如下。

void get_next(string &s){
    int l=s.size(); // l指s的长度
    nxt[0]=0; // 0...0没有真前缀/真后缀
    for (int i=1;i<l;i++){
        //对于[1,l)的每一个字符，计算它的next
        int t=nxt[i-1]; //t是拟用作next[i]的数据
        while (t && s[i]!=s[t]) //如果t不能用作next[i]
            t=nxt[t-1]; //就寻找下一个可以用作next[i]的t
        if (s[t]==s[i]) //这里检查结束循环的原因
            nxt[i]=t+1; //如果是因为s[i]==s[t]跳出了循环，就说明t+1可以作为next[i]
        else
            nxt[i]=0; //如果是因为t==0跳出了循环，说明next[i]只能是0
    }
}

求\text{next}数组这一最艰巨的任务（大雾）已经完成，下面就是比较简单的匹配过程了。

我们用i指针代表当前扫描到的主字符串的位置，j指针代表当前扫描到的模式串的位置。需要注意的有两点，一是出现失配、j指针回退时，一定要注意判断j=0的边界情况，防止死循环；二是如果恰好出现i=\text{len}(a),j=\text{len}(b)的情况，应在循环结束后额外判断。

最后指出一点，洛谷的模板题实质上是\text{MP}算法而不是\text{KMP}算法，真正的\text{KMP}还要对\text{next}数组做一些小优化（见这篇题解），但是两者在复杂度上没有差别，因此不再深究。

#include <iostream>
#include <cstdio>
#include <string>
#define MAXN 1000005
using namespace std;
int nxt[MAXN]={0};
void get_next(string &s);
int main(void){
    string a,b;
    int i,j;
    int la,lb;
    cin >> a >> b;
    get_next(b);
    la=a.size(),lb=b.size();
    i=j=0;
    while (i<la){
        //Ready to match.
        if (j==lb){
            //Match successfully.
            cout << i-lb+1 << endl;
            j=nxt[j-1];
        }
        //Try to match here!
        if (a[i]==b[j])
            i++,j++;
        else {
            if (j)
                j=nxt[j-1];
            else
                i++;
        }
    }
    //Match successfully at the end.
    if (i==la && j==lb)
        cout << i-lb+1 << endl;
    for (int i=0;i<lb;i++)
        cout << nxt[i] << ' ';
    cout << endl;
    return 0;
}

void get_next(string &s){
    int l=s.size();
    nxt[0]=0;
    for (int i=1;i<l;i++){
        int t=nxt[i-1];
        while (t && s[i]!=s[t])
            t=nxt[t-1];
        if (s[t]==s[i])
            nxt[i]=t+1;
        else
            nxt[i]=0;
    }
}

等一下，这篇文章还没完！如果\text{KMP}只能用于字符串匹配，那我还学它干什么！（大雾）\text{KMP}还有一个重要的应用：求解与恋爱循环有关的问题。

假设我们想要求一个字符串的最小循环节，如"abcabcabcabc"的最小循环节是"abc"，"aaaaaaaa"的最小循环节是"a"，朴素的方法应该是进行\text{O}(n^{2})的枚举，但是有了\text{KMP}（的\text{next}数组），\text{O}(n)就可以解决问题！

来看一个定理。

定理 22.33 恋爱循环定理

设一个字符串\text{s}[0...n-1]的长度为n，如果\text{next}[n-1]\neq 0，且(n-\text{next}[n-1])\mid n，即n\equiv 0\pmod{n-\text{next}[n-1]}，那么这个字符串是真循环的（即循环次数大于1），且最小循环节的长度是n-\text{next}[n-1]，循环次数是\frac{n}{n-\text{next}[n-1]}。 逆命题亦成立，即若一个真循环的字符串\text{s}[0...n-1]的最小循环节长度为t，则\text{next}[n-1]=n-t，且有t\mid n。

证明： 不妨设l=\text{next[}n-1\text{]}，设t=n-l，设n=kt(k\in \mathbb{N})。

由于l\neq 0，又由\text{next}数组中元素的非负性（即l\ge 0），知t < n。

我们又有t\mid n，由整除的性质，我们可以得到n\ge 2t，即k\ge 2。

由于l=n-t=kt-t=(k-1)t，我们知道t\mid l。

由于t是l和n的公因数，我们可以把\text{s}[0...n-1]均分成k节，每一节的长度都是t；也可以把\text{s}[0...l-1]（最长公共前缀）和\text{s}[n-l...n-1]（最长公共后缀）均分成k-1节，每一节的长度也都是t。

下面我们把\text{s}[0...n-1]被均分成的k节称作a_{1},a_{2},\cdots,a_{k}，把\text{s}[0...l-1]被均分成的k-1节称作b_{1},b_{2},\cdots,b_{k-1}，把\text{s}[n-l...n-1]被均分成的k-1节称作c_{1},c_{2},\cdots,c_{k-1}。

由\text{next}数组的定义，我们知道b_{1}=c_{1},b_{2}=c_{2},\cdots,b_{k-1}=c_{k-1}。

经过仔细比对下标范围（其实不那么仔细也可以），我们又发现a_{1}和b_{1}是同一个字符串（即它们代表着\text{s}字符串中同一个字串，不只是内容相同，位置也完全相同）。

经过归纳得出a_{i}和b_{i}是同一个字符串，其中i\in \{i\in \mathbb{N} \mid 1\le i \le k-1\}。同理，a_{i+1}和c_{i}是同一个字符串，其中i\in \{i\in \mathbb{N} \mid 1\le i \le k-1\}。

由b_{1}=c_{1}我们知道a_{1}=a_{2}，由b_{2}=c_{2}我们知道a_{2}=a_{3}，由b_{k-1}=c_{k-1}我们知道a_{k-1}=a_{k}，因此a_{1}=a_{2}=\cdots=a_{k}。即\text{s}[0...t-1]是\text{s}的一个循环节。

如何证明这是最小循环节呢？我们考察一个循环字符串，设它的最小循环节为"a"，设"a"的长度为t'，那么整个循环字符串可以表示为"aaaa...aa"(k个"a")，则n=kt'。容易发现，这个字符串的最长公共前后缀是"aaaa...a"(k-1个"a")，即l=(k-1)t'，此时有t=n-l=t'，因此我们按照上面的方法计算出的循环节长度t和实际最小循环节长度t'是相等的，这就说明我们计算出的t正是最小循环节长度。

循环次数显然为\frac{n}{t}。

整理可知，原命题和逆命题都已证毕。

下面附一张图以方便理解。

现在我们再来解决一个问题。如果一个字符串现在不是真循环字符串，我们现在可以在它的末尾补上若干个字符以使它成为真循环字符串，那么我们至少要补多少个字符呢？

这个问题其实也不难。要让它成为真循环字符串，只要让它满足恋爱循环定理的条件即可，即让(n-\text{next}[n-1])\mid n成立。很显然，我们应该努力让\text{next}[n-1]尽量增大，因此我们补的字符应该是最大公共前缀以后的字符，例如"abcabcefgabcabc"的最大公共前缀是"abcabc"，那么我们就应该给它补上"efg"。这么补的结果就是，n和l同时增大相同的数值，于是t的值不变。

现在问题就转化成：求一个最小的正整数x，使得t\mid (n+x)。答案很显然，x=t-n\%t。于是我们就知道，至少要补上t-n\%t个字符，才能使这个字符串成为真循环字符串。问题解决。

总之，\text{KMP}算法能够快速进行字符串的匹配，而且\text{next}数组也有许多神奇的功能，因此我们应该很好地掌握\text{KMP}（大雾）。

练习

\text{KMP}模板
求周期模板题（数据范围比较小，但是可以作为练习）
\text{next}数组的应用1（此题使用倍增算法也可以勉强过，这里涉及到一个倍增数组（二维数组）的维数优化技巧。）
\text{next}数组的应用2（此题中的周期和上文所述的周期不同。记得开\text{long long}！）

上述两个\text{next}数组的应用主要是用\text{next}数组遍历所有公共前后缀，即可以把\text{next}数组的内容理解为一棵“公共前后缀树”。