很好的hack,使前面最慢57ms的代码TLE
查看原帖
很好的hack,使前面最慢57ms的代码TLE
1371820
_Douglas_MacArthur楼主2025/7/26 16:36
#include<bits/stdc++.h>
using namespace std;
struct node{
	int s,g;
};
int n,m,z,zz,h[1919810],zzz,s,p=0;
char a[1000010],b[1000010];
vector<int>shu;
queue<node>q;
int main(){
//	freopen("P3375_1.in","r",stdin);
//	freopen("3375_2.out","w",stdout);
	scanf("%s",a+1);
	scanf("%s",b+1);
	z=strlen(a+1);
	zz=strlen(b+1);
//	b=' '+b;
//	a=' '+a;
	s=z-zz;
	for(int i=2;i<=zz;++i){
		if(b[i]==b[1]){
			shu.push_back(i);
		}
	}
	zzz=shu.size();
	for(int i=0;i<zzz;++i){
		m=shu[i];
//		if(!h[m]){
			while(b[m-shu[i]+1]==b[m]){
				m++;
				h[m-1]=max(h[m-1],m-shu[i]);
			}
//		}
	}
	for(int i=1;i<=z;i++){
		while(a[i]!=b[p+1]&&p){
			p=h[p];
		}
		if(a[i]==b[p+1]){
			p++;
		}
		if(p==zz){
			printf("%d\n",i-zz+1);
			p=h[p];
		}
	}
	for(int i=1;i<=zz;++i){
		printf("%d ",h[i]);
	}
	return 0;
}

2025/7/26 16:36
加载中...