关于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\)
\(next\)定义：其中\(next_i\)表示\(A\)中以\(i\)结尾的非前缀(即长为i前缀的真后缀)子串与\(A\)的真前缀（其实只要有一个加‘真“字就好了）能够匹配的最长长度
解释：在字符串中，我们称一个字符串的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
感谢观看。