前缀函数定义对于一个长度为nnn的字符串sss前缀数组π[i]\pi[i]π[i]的定义是如果子串s[0…i]s[0\dots i]s[0…i]有至少一对相等的真前缀和真后缀s[0…k−1]s[i−k1…i]s[0\dots k-1] s[i-k1\dots i]s[0…k−1]s[i−k1…i]那么π[i]\pi[i]π[i]就是所有满足条件的kkk的最大值也就是最长的相等前后缀的长度。真前缀、真后缀的意思就是这个前缀/后缀不能包含整个字符串也就是整个子串s[0…i]s[0\dots i]s[0…i]也不能是空的。如果没有相等的那就等于000。π[0]\pi[0]π[0]也默认是000因为s[0]s[0]s[0]没有真前缀或者真后缀它总共就一位无论怎么选都会包含整个字符串。假设在这个串当中我们要求最后一位的π\piπ值aabacaabaaabacaabaaabacaaba这里前缀前四位aabaaabaaaba和后缀最后四位aabaaabaaaba是一样的所以π[i]4(i8)\pi[i]4(i8)π[i]4(i8)。虽然第一位aaa和最后一位aaa也是一对合法的前后缀但是它们的长度只有111π[i]\pi[i]π[i]只会取最大的长度。对于其他位置π[0]0, π[1]0, π[2]0, π[3]1 (a), π[4]0, π[5]1 (a), π[6]2 (aa), π[7]3 (aab)\pi[0]0,\,\pi[1]0,\,\pi[2]0,\,\pi[3]1\,(a),\,\pi[4]0,\,\pi[5]1\,(a),\,\pi[6]2\,(aa),\,\pi[7]3\,(aab)π[0]0,π[1]0,π[2]0,π[3]1(a),π[4]0,π[5]1(a),π[6]2(aa),π[7]3(aab)。当然被选中的前后缀也可以重叠比如这个串ababaababaababa最后一位的π[i](i4)\pi[i](i4)π[i](i4)就等于333是前三位abaabaaba和后三位abaabaaba它们相等并且共用了正中间的aaa。接下来要考虑怎么求π\piπ建议先自己考虑一会儿尝试得出求法。理想情况直接 1聪明的小伙伴已经发现了最简单的情况可以直接借用π[i]\pi[i]π[i]来得到π[i1]\pi[i1]π[i1]。如下图所示蓝色是表示π[i]\pi[i]π[i]匹配到的前后缀s[0…π[i]−1]s[0\dots\pi[i]-1]s[0…π[i]−1]就是π[i]\pi[i]π[i]匹配到的最长前缀。粉色部分是尝试匹配新的一位s[i1]s[i1]s[i1]如果s[i1]s[π[i]]s[i1]s[\pi[i]]s[i1]s[π[i]]那不就刚好把前缀往后延长了一位后缀在i−π[i]1i-\pi[i]1i−π[i]1到iii的基础上也往后延长一位然后这多出来的两位刚好匹配上了前半部分之前在求π[i]\pi[i]π[i]的时候已经确认过匹配得上是一对合法的前后缀所以π[i1]π[i]1\pi[i1]\pi[i]1π[i1]π[i]1。有没有可能让π[i1]\pi[i1]π[i1]更大呢那就说明相等的前后缀还要再延长变成下图中的两个红括号的范围假设它们是相等的也就是π[i1]\pi[i1]π[i1]可以更大看看会发生什么。如果它们相等那么π[i]\pi[i]π[i]就应该比原来更大就不是我们用来推π[i1]\pi[i1]π[i1]的那个π[i]\pi[i]π[i]了所以不可能。原因是如果设红括号选中的长度为k(kπ[i1]π[i]1)k(k\pi[i1]\pi[i]1)k(kπ[i1]π[i]1)则红括号当中的前k−1k-1k−1位也一定相等也就是s[0…k−2]s[0\dots k-2]s[0…k−2]和s[i−k2…i]s[i-k2\dots i]s[i−k2…i]是相等的它们作为一对相等的前后缀就说明π[i]\pi[i]π[i]可以等于k−1k-1k−1而kπ[i]1, k−1π[i]k\pi[i]1,\,k-1\pi[i]kπ[i]1,k−1π[i]。我们这里得出这个结论π[i1]≤π[i]1\pi[i1]\le\pi[i]1π[i1]≤π[i]1一会儿算时间复杂度有用。情况不太理想怎么办现在我们尝试匹配s[π[i]]s[\pi[i]]s[π[i]]和s[i1]s[i1]s[i1]结果它们对不上如下图粉色是我们尝试匹配的但是它们一个是eee一个是bbb不相等。蓝色横线是前面一位π[i]\pi[i]π[i]匹配到的前后缀两者相等。[下面这段讲解基于下面那张比较简陋的图可以对照上面那张图的一些下标信息来理解]这时候π[i]1\pi[i]1π[i]1肯定是没希望了那么比它更小的长度有哪个是能匹配上的呢我们现在要找到一个点它在i−π[i]1i-\pi[i]1i−π[i]1的后面从这个点到当前位置i1i1i1作为后缀然后前面找一个比π[i]\pi[i]π[i]更短的前缀让两个串尝试匹配。这两个短一点的串在下图中用紫色的括号括起来了蓝色横线和上图中代表同样的意思粉色是s[i1]s[i1]s[i1]。那么这两段紫色的要相同就说明这两段紫色当中去掉最后一位粉色得到的绿色线段也要相同。根据蓝色横线画的部分是相同的可以得到右侧蓝色线段下面最右边的绿色线段又和左侧蓝色线段最右边的那一段墨绿色线段相同。也就是说这三条绿色的线段画出来的地方都是相同的。等一下我们现在只看左边那条蓝色线下面的两个绿色线段它们相同的话…它们刚好是一对前后缀嘛蓝色线段的最右边的位置是π[i]−1\pi[i]-1π[i]−1这两条绿色线段刚好是π[π[i]−1]\pi[\pi[i]-1]π[π[i]−1]的匹配情况啊如果要让紫色线段π[i1]\pi[i1]π[i1]更长粉色的位置只有一个排除掉它之后就是要让绿色的线段更长绿色线段的最大长度就是在s[0…π[i]−1]s[0\dots\pi[i]-1]s[0…π[i]−1]当中最长的匹配前后缀刚好是π[π[i]−1]\pi[\pi[i]-1]π[π[i]−1]。那我们就可以尝试匹配粉色的i1i1i1和左边有一个粉色点的位置如果它们s[π[π[i]−1]], s[i1]s[\pi[\pi[i]-1]],\,s[i1]s[π[π[i]−1]],s[i1]相等就代表两个紫色线段相等可以让π[i1]π[π[i]−1]1\pi[i1]\pi[\pi[i]-1]1π[i1]π[π[i]−1]1。[上面图中橙色的部分是π[π[i]−1]\pi[\pi[i]-1]π[π[i]−1]的匹配结果和这里的绿色线段一样。红色方框就是尝试匹配的两个位置和这里的两个粉色点一样]如果这样两个粉色点还是匹配不上那就只能再跳到π[π[π[i]−1]−1]\pi[\pi[\pi[i]-1]-1]π[π[π[i]−1]−1]去试一下能不能继承π[π[π[i]−1]−1]\pi[\pi[\pi[i]-1]-1]π[π[π[i]−1]−1]的值了。每次迭代都是先减一再套一个π[]\pi[]π[]如果都跳到000了还匹配不上就直接让π[i1]0\pi[i1]0π[i1]0。时间复杂度分析我们考虑当前位置π[i1]\pi[i1]π[i1]的增加和减少。最大的情况是比前面一个增加111其他时候让π[i1]\pi[i1]π[i1]的初始值等于π[i]1\pi[i]1π[i]1每迭代一次从π[i]\pi[i]π[i]变成π[π[i]−1], π[π[π[i]−1]−1]\pi[\pi[i]-1],\,\pi[\pi[\pi[i]-1]-1]π[π[i]−1],π[π[π[i]−1]−1]都会让π[i1]\pi[i1]π[i1]至少减掉111能减的次数最多是π[i]1\pi[i]1π[i]1。如果在π[i1]\pi[i1]π[i1]上迭代了很多次用了很多时间那么π[i1]\pi[i1]π[i1]就会很小到π[i2]\pi[i2]π[i2]的时候初始值太小就减不了几次了。因为每个π[i1]\pi[i1]π[i1]只基于前面一个π[i]\pi[i]π[i]的值来决定加和减的次数整个过程中只会进行n∣s∣n|s|n∣s∣次111同样也最多只能进行nnn次−1-1−1所以时间复杂度是O(n)O(n)O(n)。KMP 算法要解决的问题是有一个字符串sss和一个字符串ttt要找ttt在sss中作为子串出现了几次在哪些位置出现。这就是一个前缀函数的基本应用很容易想到建议读者自己想。很简单就是在字符串sss前面把ttt放进去然后在ttt和sss之间隔一个不会出现的字符比如 #。举个例子sabcbabc, tab - ab#abcbabc。求出所有前缀函数找到所有π[i]∣t∣(i∣t∣)\pi[i]|t|(i|t|)π[i]∣t∣(i∣t∣)ttt在原本的sss中出现的开始下标就是i−∣t∣1−(∣t∣1)i−2∣t∣i-|t|1-(|t|1)i-2|t|i−∣t∣1−(∣t∣1)i−2∣t∣。代码实现#includebits/stdc.h#pragmaGCCoptimize(O3,unroll-loops)#pragmaGCCtarget(avx2,bmi,bmi2,lzcnt,popcnt)usingnamespacestd;#definelllonglong#defineendl\nstring s,t;intp[3000005];intmain(){ios::sync_with_stdio(0);cin.tie(0);cinst;//kmpst#s;for(inti0;i1s.size();i){intji;while(j0){if(s[p[j]]s[i1]){p[i1]p[j]1;break;}jp[j]-1;}}intsitt.size();for(intisit1;is.size();i)if(p[i]sit)couti-2*sit1endl;//求字符串 t 的前缀数组memset(p,0,sizeof(p));for(inti0;i1sit;i){intji;while(j0){if(t[p[j]]t[i1]){p[i1]p[j]1;break;}jp[j]-1;}}for(inti0;isit;i)coutp[i] ;coutendl;return0;}/* input: eeaccbbacceaccbbaccbaccbaccbbacceaccbbaccbaccbac accbbacceaccbbaccbaccbac output: 3 25 0 0 0 0 0 1 2 3 0 1 2 3 4 5 6 7 8 4 1 2 3 4 1 2 */上面经历了很多奇怪的证明和抽象的绘画希望大家看懂了推荐各位去本文所在的专栏中的下面一篇文章继续学习。