UN快乐暑假（五）—— （自闭多校）扩展KMP

本文主要是介绍UN快乐暑假（五）—— （自闭多校）扩展KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

又双叒叕在多校get新算法
扩展KMP
（以下转载自博客:https://blog.csdn.net/dyx404514/article/details/41831947）

拓展kmp是对KMP算法的扩展，它解决如下问题：

定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extendi。

注意到，如果有一个位置extend[i]=m,则表示T在S中出现，而且是在位置i出现，这就是标准的KMP问题，所以说拓展kmp是对KMP算法的扩展，所以一般将它称为扩展KMP算法。

下面举一个例子，S=”aaaabaa”,T=”aaaaa”,首先，计算extend[0]时，需要进行5次匹配，直到发生失配。
[外链图片转存失败(img-BTKQjJDk-1565016673638)(https://i.loli.net/2019/08/05/CYcfzt7ExuDUSgI.png)]

从而得知extend[0]=4，下面计算extend[1],在计算extend[1]时，是否还需要像计算extend[0]时从头开始匹配呢？答案是否定的，因为通过计算extend[0]=4，从而可以得出S[0,3]=T[0,3]，进一步可以得到 S[1,3]=T[1,3],计算extend[1]时，事实上是从S[1]开始匹配，设辅助数组next[i]表示T[i,m-1]和T的最长公共前缀长度。在这个例子中，next[1]=4,即T[0,3]=T[1,4],进一步得到T[1,3]=T[0,2],所以S[1,3]=T[0,2],所以在计算extend[1]时，通过extend[0]的计算，已经知道S[1,3]=T[0,2],所以前面3个字符已经不需要匹配，直接匹配S[4]和T[3]即可，这时一次就发生失配，所以extend[1]=3。这个例子很有代表性，有兴趣的读者可以继续计算完剩下的extend数组。

1. 拓展kmp算法一般步骤

通过上面的例子，事实上已经体现了拓展kmp算法的思想，下面来描述拓展kmp算法的一般步骤。

首先我们从左到右依次计算extend数组，在某一时刻，设extend[0…k]已经计算完毕，并且之前匹配过程中所达到的最远位置为P，所谓最远位置，严格来说就是i+extend[i]-1的最大值（0<=i<=k）,并且设取这个最大值的位置为po，如在上一个例子中,计算extend[1]时，P=3，po=0。

[外链图片转存失败(img-SrT4m6R0-1565016673641)(https://i.loli.net/2019/08/05/lvL3EW74JwMbQGp.png)]

现在要计算extend[k+1],根据extend数组的定义，可以推断出S[po,P]=T[0,P-po],从而得到 S[k+1,P]=T[k-po+1,P-po],令len=next[k-po+1]，(回忆下next数组的定义),分两种情况讨论：

第一种情况：k+len<P

如下图所示：

上图中，S[k+1,k+len]=T[0,len-1]，然后S[k+len+1]一定不等于T[len]，因为如果它们相等，则有S[k+1,k+len+1]=T[k+po+1,k+po+len+1]=T[0,len],那么next[k+po+1]=len+1，这和next数组的定义不符(next[i]表示T[i,m-1]和T的最长公共前缀长度)，所以在这种情况下，不用进行任何匹配，就知道extend[k+1]=len。

第二种情况： k+len>=P

如下图：
[外链图片转存失败(img-DkjbH9te-1565016673644)(https://i.loli.net/2019/08/05/8ZxqDHMazOt3Cj2.png)]

上图中，S[p+1]之后的字符都是未知的，也就是还未进行过匹配的字符串，所以在这种情况下，就要从S[P+1]和T[P-k+1]开始一一匹配，直到发生失配为止，当匹配完成后，如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。

至此，拓展kmp算法的过程已经描述完成，细心地读者可能会发现，next数组是如何计算还没有进行说明，事实上，计算next数组的过程和计算extend[i]的过程完全一样，将它看成是以T为母串，T为字串的特殊的拓展kmp算法匹配就可以了，计算过程中的next数组全是已经计算过的，所以按照上述介绍的算法计算next数组即可，这里不再赘述。

2. 时间复杂度分析

下面来分析一下算法的时间复杂度，通过上面的算法介绍可以知道，对于第一种情况，无需做任何匹配即可计算出extend[i]，对于第二种情况，都是从未被匹配的位置开始匹配，匹配过的位置不再匹配，也就是说对于母串的每一个位置，都只匹配了一次，所以算法总体时间复杂度是O(n)的，同时为了计算辅助数组next[i]需要先对字串T进行一次拓展kmp算法处理，所以拓展kmp算法的总体复杂度为O(n+m)的。其中n为母串的长度，m为子串的长度。

本次杭电多校的题目是求比较了多少次，其实就是求next[]数组，我一开始以为是把next_数组累加，然后加上字符串长度减去1就可以了，意思是指每一次匹配最长前缀的次数再加上失配的一次。

但是，有时K会一直比较到最后一位len-1，这样就可能在比较完前缀的时候没有失配的那一次，所以要在pre_exkmp里来根据不同的情况来直接计数。

代码：

/*
扩展KMP
next_[i]: P[i..m-1] Óë P[0..m-1]µÄ×¹«¹²Ç°×º
ex[i]: T[i..n-1] Óë P[0..m-1]µÄ×¹«¹²Ç°×º
*/
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#define ll long long
using namespace std;
const int Max = 1e6 + 10;
char T[Max],P[Max];
int next_[Max],ex[Max];
int n,cas;
ll ans = 0;void pre_exkmp(char P[]) {int m=strlen(P);next_[0]=m;int j=0,k=1;while(j+1<m&&P[j]==P[j+1]) j++;next_[1]=j;ans += next_[1];if(next_[1] != m - 1) ans++;for(int i=2; i<m; i++) {int p=next_[k]+k-1;int L=next_[i-k];if(i+L<p+1) next_[i]=L;else {j=max(0,p-i+1);while(i+j<m&&P[i+j]==P[j]) j++;next_[i]=j;k=i;}ans += next_[i];if(next_[i] != m - i) ans++;}
}void exkmp(char P[],char T[]) {int m=strlen(P),n=strlen(T);pre_exkmp(P);int j=0,k=0;while(j<n&&j<m&&P[j]==T[j]) j++;ex[0]=j;for(int i=1; i<n; i++) {int p=ex[k]+k-1;int L=next_[i-k];if(i+L<p+1) ex[i]=L;else {j=max(0,p-i+1);while(i+j<n&&j<m&&T[i+j]==P[j]) j++;ex[i]=j;k=i;}}
}int main() {scanf("%d",&cas);while(cas--) {getchar();scanf("%s",P);int len = strlen(P);ans = 0;pre_exkmp(P);printf("%lld\n",ans);}}

1006等推出规律再更新

这篇关于UN快乐暑假（五）—— （自闭多校）扩展KMP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---