CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====扩展kmp=====
====简介====
定义母串 $S$，和字串 $T$，设 $S$ 的长度为 $n，T$ 的长度为 $m$ ，求 $T$ 与 $S$ 的每一个后缀的最长公共前缀，也就是说，设 $extend$ 数组, $extend[i]$ 表示 $T$ 与 $S[i,n-1]$ 的最长公共前缀，要求出所有 $extend[i](1\le i\le n)$。
====代码====
<hidden>
<code cpp>
l1=strlen(a+1),l2=strlen(b+1);
nxt[1]=l2;
i=1;
while(b[i]==b[i+1]&&i+1<=l2) i++;
nxt[2]=i-1;
pos=2;
for(i=3;i<=l2;i++){
	if(pos+nxt[pos]>=i) nxt[i]=min(nxt[i-pos+1],pos+nxt[pos]-i);
	while(b[nxt[i]+1]==b[nxt[i]+i]) nxt[i]++;
	if(nxt[i]+i>pos+nxt[pos]) pos=i; 
}
pos=1;
int l=min(l1,l2);
for(i=1;i<=l;i++) {
	if(a[i]!=b[i]) break;
	extend[1]=i;
}
for(i=2;i<=l1;i++){
	if(pos+extend[pos]>=i) extend[i]=min(nxt[i-pos+1],pos+extend[pos]-i);
	while(extend[i]+1<=l2&&extend[i]+i<=l1&&b[extend[i]+1]==a[extend[i]+i]) extend[i]++;
	if(extend[i]+i>pos+extend[pos]) pos=i; 
}
</code>
</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具