用途

对于串\(s1,s2\)，可以求出\(s2\)与\(s1\)的每个后缀的最长公共前缀。

（其实SA也可以干这事，只不过复杂度多个\(\log\)可能会被卡）

思想

与kmp一样，主要是充分利用已经得到的信息来往下推，以降低复杂度。

暴力

\(O(n^2)\)暴力扫，相信大家都会？

优化

记\(s[l,r]\)表示\(s\)在\([l,r]\)的子串。

考虑这样一件事：假如\(s2[1,k]=s1[1,k]\)，那么就可以知道\(s2[2,k]=s1[2,k]\)。

假如再知道\(s2[2,p]=s2[1,p-1]\)，那么就可以推出\(s2[1,\min(p,k)-1]=s1[2,k]\)了。

\(s2[2,p]=s2[1,p-1]\)正是kmp中\(s2\)的\(nxt\)数组，于是这样就可以完成一次转移。

然而这样转移并不是很优：当\(p<k\)时显然不能再往后推，但\(p>k\)时往后推还需要\(O(n)\)的时间，总复杂度仍然是\(O(n^2)\)的。

但我们可以记录之前最大的\(k\)在哪里，于是\(k_{max}\)单调递增，复杂度就有保证了。

代码

由于求nxt和求ex代码非常像，于是缩到了一起。

int n,m;

char s1[sz],s2[sz];

int nxt[sz],ex[sz];

void ExKmp(char *s1,char *s2,int *nxt,int *ex)

{

	int len1=strlen(s1+1),len2=strlen(s2+1);

	if (s1!=s2) for (ex[1]=0;s1[ex[1]+1]==s2[ex[1]+1]&&ex[1]<min(len1,len2);ex[1]++);

	else {nxt[1]=len1;while (s1[nxt[2]+1]==s1[nxt[2]+2]&&nxt[2]+2<=len1) ++nxt[2];}

	int p=1+(s1==s2);

	rep(i,2+(s1==s2),len1)

	{

		if (i+nxt[i-p+1]<p+ex[p]) ex[i]=nxt[i-p+1];

		else

		{

			int k=max(p+ex[p]-i,0);

			while (s1[i+k]==s2[k+1]) ++k;

			ex[i]=k;p=i;

		}

	}

} 

int main()

{

	file();

	cin>>(s1+1)>>(s2+1);

	n=strlen(s1+1),m=strlen(s2+1);

	ExKmp(s2,s2,nxt,nxt);ExKmp(s1,s2,nxt,ex);

	rep(i,1,m) printf("%d ",nxt[i]);

	puts("");

	rep(i,1,n) printf("%d ",ex[i]);

	return 0;

}

巴特西

扩展kmp学习笔记

用途

思想

暴力

优化

代码

最新文章

热门文章