关于KMP

· · 闲话

关于KMP

    平凡，而又不平凡的一天，12月31日，2022年的最后一天，让我们用几句代码迎接新年的到来。

cout<<"Good bye 2022\n";
printf("Hello 2023!");

    扯正题。

Kmp的简介

    KMP算法是字符串匹配算法，基础的用途是在文本串中快速查找与模式串相匹配的位置。

一些感想

我们在研究这个算法的时候，和之前不同，这次我们会遇到大量定义，而且如果不深入思考，会觉得这些定义莫名其妙，也会遇到一些引理啥的。如果光看书（我指的是《算法竞赛进阶指南》，如果没有意外，之后的“书”都是指这本），那么看看他长达4页的论述，再加上定义一层套一层，就会出现看一上午看了个寂寞的情况（反正这是我第二回学KMP，第一回就是这样）。

又一些感想[Update at 2023/1/15]

与同学(巨佬@l_h_l%%%)交流之后才知道，我这第二回看KMP，看了一上午，写了一上午，又看了个寂寞。这些解释完全是肤浅幼稚的，只适合完全无法理解算法“如何做到”的人来看，只是照着步骤解释步骤，而没有深入到底层理解算法“为什么这么做”、“优化了什么”、“怎么想出来的”这些真正对提升思维有帮助的内容。所以我滚回来填坑了。

准备工作-前缀函数

这里直接参考书上

对模式串A(长为N)进行自我匹配，求出数组next

解释：在字符串中，我们称一个字符串的border，即该字符串的**真前缀**和**真后缀**相同的最长长度（注意，真前缀和真后缀指的都是不包括字符串本身的前缀和后缀，否则就一定有一个border是字符串本身），在这里$next_N$数组的定义就相当于border，$next_i$就是该字符串前i个的最长border 例如，如果有字符串$S$="112211",那么$next_2=1$(即字符1),$next_3=0,next_4=0,next_5=0,next_6=2$(即"11")

在这里next就是标题里说的前缀函数。这还没有到KMP的地界。但是KMP算法需要前缀函数。所以我们先考虑如何高效地求前缀函数。

由于暴力算法很简单，这里不讨论。

//OI-Wiki Version
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = i; j >= 0; j--)
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

我们有两个优化：

优化一 相邻的函数值要么增加1，要么不变或变少

因为只增加了一个字符，根据定义，border的长度（即next）最多增加1，或是由于真后缀被打断而减少

那么，我们在考虑求解next_i的时候就很可能可以用到之前的数据来求（对，类似于递推）

现在假如要把next数组后推一位，如果考虑增加1，那么就必须要求新的border增加的字符必须匹配。

例如，字符串S="abaaba", 现在如果求出了next_{1...5},现在next_5显然等于2（”ab“）

后推一位求next_6。新添加的字符S[6]"a"与S[next_5+1]是匹配的，那么next_6=next_5+1

优化二

可以发现，优化一中只讨论了，S[i]=S[next_{i-1}+1]的最好情况，让我们继续看看其他情况。

如果S[i]\not=S[next_{i-1}+1],就必须继续考虑。

会发现，我们单独列出了优化一这个看似没有讨论完全的结论，其实我们可以继续推广，上面我们使用了递推的思想，接下来让我们使用递归的思想。

我们将S[i]\not=S[next_{i-1}+1]这种情况称为”失配“

于是，根据上面每一次只能增加1的这种思路，想要求next_i尽可能大，我们放弃从next_{i-1}扩展，我们希望找到仅次于next_{i-1}的一个border（原书称为”候选项“）

这里有一个引理，就是”next_{next_{i-1}}\text{到}next_{i-1}中间没有其他”候选项“，即next_{next_{i-1}}是仅次于next_{i-1}的候选项“

证明：如果next_{next_{i-1}}=R\text{到}next_{i-1}中间还有”候选项“，设该候选项为X(显然R<X)

根据next的定义，S[0...i-1]的前R项和后R项当然相等，而他的前X项和后X项当然也相等，然鹅R<X，这意味着前R项是前X项的子串，后R项也是后X项的子串。那么X显然优于R，则next_{next_{i-1}}=X，矛盾。原命题得证。

也就是说，我们只要在”失配“的时候往前”跳“，继续匹配第二位的”候选项“...如果都没有匹配成功，就说明next_i=0。

这就像是递归一样。

例子：字符串S="abaaba",当求出了next_{1...3}求next_4时,显然next_3=1，发现S[next_{4-1}+1=2]\not=S[4](一个是”b“，一个是”a“)，此时跳到next_{next_{3}}=0来考虑，由于next_{next_3}+1=1,S[1]="a"=S[4]所以next_4=next_{next_3}+1=1。

懂了吗？

next数组的求法可谓是递推递归思想的完美结合，认真体会，乐趣无穷。

另外，结合“候选项”对比朴素算法可知，前缀函数优化就是一个减小解空间的过程。

代码

激动人心的放代码环节

    fail[1]=0;//第一个没有border,注意必须是真前缀真后缀
    for(int i=2;i<=lenb;i++){//自己与自己匹配
        while(pos&&b[pos+1]!=b[i]) pos=fail[pos];//失配了,不断向前跳
        if(b[pos+1]==b[i]){//如果匹配成功
            pos++;//如果成功就加1
        }//最后都没有成功,pos为0
        fail[i]=pos;//设置当前fail为匹配到的位置pos
    }

注：这里的fail就是next数组

KMP

到了这里，KMP就已经水到渠成了。

设模式串为M,文本串为T ,构造字符串S=M+F+T,其中，字符F是既不在M也不在T内的一个”分隔符“。

按照上面的方法求S的前缀函数next，那么由于分隔符F的存在，F以后的前缀函数值不可能超过|M|（M的长度），根据定义，F以后的next_i值就是说，M的长为next_i的前缀在i位置出现了（以后缀形式）。那么，若next_i=|M|，就意味着M在这里出现了。

代码：

pos=0;
    for(int i=1;i<=lena;i++){
        while(pos&&b[pos+1]!=a[i]) pos=fail[pos];//失配了往前跳
        if(b[pos+1]==a[i]){
            pos++;//同上
        }
        //f[i]=pos; //T的前缀函数
        if(pos==lenb){//如果完全匹配
            cout<<i-lenb+1<<endl;//这里找到M出现位置，直接输出
            pos=fail[pos];
       //这里要跳是因为要找所有出现，像书上的写法因为在while里加了判断所以不需要专门跳
        }
    }

如上代码所示，我们没有真的去拼接M和T，只是把自我匹配中的后缀换成了T的后缀，过程基本一致。这里没有存储书上说的f是因为原题中不需要（如注释所示）。

同样fail代表next。

算法的时间复杂度为O(n+m)

算法思想

看完了KMP，有没有想过几个问题：

那么，K、M、P这三个计算机科学家，是怎么想的呢？

首先，我们看看如果是一个正常人，去匹配两个字符串，会做什么？

EOF

感谢观看。

\Huge{QwQ}