KMP,有取最小值操作,自己分析O(n),tle on #3求助
查看原帖
KMP,有取最小值操作,自己分析O(n),tle on #3求助
279095
gargantuar楼主2021/9/14 10:55
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
//	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=var
int n,la,lb,kmp[1114514];
char a[1114514],b[1114514];
//	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=
int main(){
	scanf("%d%s",&n,a+1);
	la=strlen(a+1);
	for(int q=2;q<=n;++q){
		scanf("%s",b+1);
		lb=strlen(b+1);
		int lc;
		for(int i=2;i<=min(la,lb);++i){
			while(lc&&b[i]!=b[lc+1])lc=kmp[lc];
			if(b[i]==b[lc+1])++lc;
			kmp[i]=lc;
		}
		lc=0;
		for(int i=la-min(la,lb)+1;i<=la;++i){
			while(lc&&a[i]!=b[lc+1])lc=kmp[lc];
			if(a[i]==b[lc+1])++lc;
		}
		for(int i=lc+1;i<=lb;++i){
			a[++la]=b[i];
		}
		for(int i=0;i<=min(la,lb);++i)kmp[i]=0;
	}
	printf("%s",a+1);
}
2021/9/14 10:55
加载中...