4824求助,哈希+栈只有16分
  • 板块学术版
  • 楼主__gcd__
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/11/27 17:07
  • 上次更新2023/11/3 23:27:00
查看原帖
4824求助,哈希+栈只有16分
311478
__gcd__楼主2021/11/27 17:07
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
ULL ans,sum[1000005],b=131,p[1000005]={1};
char s1[1000005],s2[1000005],da[1000005];
int main(){
	cin>>s1+1>>s2+1;
	for(int i=1;i<1000005;i++)
	  p[i]=p[i-1]*b;
	int la=strlen(s1+1),lb=strlen(s2+1);
	for(int i=1;i<=lb;i++)
	{
		ans=ans*b+(ULL)(s2[i]);
	}
	int len=0;
	for(int i=1;i<=la;i++){
		sum[++len]=sum[len-1]*b+(ULL)(s1[i]);
		da[len]=s1[i];
		if(ans==sum[len]-sum[len-lb]*p[lb])
		  len-=lb;
	}
	for(int i=1;i<=len;i++)
	  cout<<da[i];
	return 0;
}

求大佬指点迷津

2021/11/27 17:07
加载中...