KMP 学习笔记

高中的时候只是迷迷糊糊地理解了一点吧，停留在了背板的层面，后来甚至连板都背不利索了。

从现在的视角来看KMP，又有新的收获。

Intro

去理解一个算法一个比较好的方式其实是建立实际意义。

为什么打游戏的时候发不出藏话？试想一下，如果你在聊天框里面输入一个 \(114514\) 长度的文本，里面的所有脏字依然能够在很短的时间里面被检测出来并屏蔽，这是怎么做到的？

解决

以下都记文本串为 \(S\) ，模式串为 \(T\)。

暴力

有一个很 naive 的想法就是，暴力地去枚举文本串的每一个开头，然后尽可能多地与模式串（藏话串）向后匹配，这样的时间复杂度是 \(O(n^2)\) 的。显然不太能够接受。

优化暴力

假设对于某个开头，已经匹配完了一定长度的串，但是在接下来的一个位置里面失配了，这里举个例子，比如 \(S=ABABABC\) ,\(T=ABABC\) 。以第 \(1\) 个位置为开头的时候，会在第 \(5\) 个位置失配，那么暴力来说，就会从第 \(2\) 个位置又从头再来，但这样有意义吗？

在这个例子中，我们实际上已经把 \([1,4]\) 位的匹配都做完了，如果第五位失配了，那你肯定会想，下一个从哪里开始匹配，可以保证不会遗漏答案的同时，又能够skip掉没有意义的环节。

显然对于 \(ABABABC\) 这个串，我们在第五位如果失配了，就会想着把已经匹配成功的 \(ABAB\) 缩短成 \(AB\) ，然后再看看后面能不能把 \(S[5]\) 拼接进来。再举一个例子，对于 \(CBCBC\) 在第 \(6\) 位失配，我们会把它缩短成 \(CBC\) ,尝试把 \(S[6]\) 拼进来。如果说拼不进来，那我们就不断重复上述缩短过程，直到剩下的串为空。

可以观察到，这样其实是截取了 **模式串 **的一个前缀串 \(S'\) 中，其前缀和后缀的最大相同部分，如果我们通过某种方式把 模式串 中所有 **前缀串 ** 的 前后最大相同部分 求出来了，那么这个匹配的过程就可以得到优化。

KMP

记对于一个前缀 \(S'=S[1]+S[2]+..+S[i]\) ，上述我们想要求得的东西是 \(nex[i]\) ，那么文本串和模式串的匹配就可以简化成如下过程：

枚举当前应该加入 \(S\) 中的哪个字符，然后不断地尝试匹配，成功之后输出能够匹配的开始位置。

    int j=0;
    for(int i=1;i<=len1;++i)
    {
        while(j&&t[j+1]!=s[i])j=nex[j];
        if(t[j+1]==s[i])j++;
        if(j==len2)
            cout<<i-j+1<<'\n';
    }

更形式化的，\(nex[i]\) 被定义为 ：前缀 \(S'\) 中最长的非空相同前后缀。

不难发现，其实这个 \(nex\) 数组的求解过程，就如同把 \(T\) 与自身进行一个匹配。

如果已经成功求出了 \(nex[i-1]\) ，那么现在加入 \(T[i]\) 这个字符，就是看能不能接上去，如果不能接上去，我们就进行 缩短 操作，利用已经求得的 \(nex\) 数组迭代，直到能够成功匹配或者变为空串为止，这就可以用如下十分相似的代码来表达：

    int j=0;nex[1]=0;
    for(int i=2;i<=len2;++i)
    {
        while(j&&t[j+1]!=t[i])j=nex[j];
        if(t[j+1]==t[i])j++;
        nex[i]=j;
    }

正确性 & 复杂度

正确性

为什么这样是不漏的？因为 \(nex\) 本身的定义就包含了一个 最长 ，那么我们失配之后（这时候还没有完成匹配）跳到的位置，一定是距离当前 最近的 、可能成为答案 的位置。

复杂度

这个复杂度其实也不太好分析，但洛谷第一篇题解写的很有道理：
“每次位置指针 \(i++\) 时，失配指针 \(j\) 最多增加一次，所以 \(j\) 至多增加 \(len\) 次，从而至多减少 \(len\) 次，因此是 \(O(n+m)\) 的。”

ExKMP（Z函数）

挖个坑寒假或者是之后来做这个板块，毕竟除了数据结构和字符串之外的基础内容也得学一学。