QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#537462#5256. InsertionsRockyYueWA 0ms21476kbC++143.4kb2024-08-30 13:57:112024-08-30 13:57:11

Judging History

你现在查看的是最新测评结果

  • [2024-08-30 13:57:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:21476kb
  • [2024-08-30 13:57:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5; const ll p0=131,MOD=1e9+7;
string rev(string s){
	string t=s; reverse(t.begin(),t.end());
	return t;
}
void getFail(string s,int *fail){
	fail[1]=0;
	int j=0,n=s.size()-1;
	for(int i=2;i<=n;++i){
		while(j!=0&&s[j+1]!=s[i])j=fail[j];
		fail[i]=(j+=s[j+1]==s[i]);
	}
}
struct Tree{
	struct edge{int v,nxt;}e[N<<1];
	int head[N]={0},cnt=0;
	void add(int u,int v){e[++cnt]={v,head[u]},head[u]=cnt;}
	int dfnl[N]={0},dfnr[N]={0},c[N]={0},times=0;
	void dfs0(int u,int fa){
		dfnl[u]=++times;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(v!=fa)dfs0(v,u);
		}
		dfnr[u]=times;
	}
	void upd(int x,int v){
		for(;x<N;x+=(x&-x))c[x]+=v;
	}
	int qry(int x){
		int res=0;
		for(;x;x-=(x&-x))res+=c[x];
		return res;
	}
}T1,T2;
void buildTree(int n,int *fail,Tree&T){
	for(int i=1;i<=n;++i)T.add(fail[i],i);
	T.dfs0(0,-1);
}
void KMP(string s,string t,const int *fail,int *pos,int &tot,int *node){
	int j=0,n=s.size()-1,m=t.size()-1; tot=0;
	for(int i=1;i<=n;++i){
		while(j!=0&&t[j+1]!=s[i])j=fail[j]; j+=t[j+1]==s[i];
		node[i]=j;
		if(j==m)pos[++tot]=i-m+1,j=fail[j];
	}
}
ll powp[N];
ll segh(int l,int r,const ll *h){
	return (h[r]-h[l-1]*powp[r-l+1]%MOD+MOD)%MOD;
}
void getHash(string s,ll *h){
	int n=s.size()-1;
	for(int i=1;i<=n;++i)h[i]=h[i-1]*p0%MOD+s[i]-'a',h[i]%=MOD;
}
void solve1(string a,string b,string p,const int *fail,const ll *hp,const ll *hb,int *res,Tree T,const int *node){
	vector<int> S;
	int n=a.size()-1,m=b.size()-1,l=p.size()-1;
	for(int i=1;i<=m&&i<l;++i){
		if(segh(1,i,hb)==segh(l-i+1,l,hp))S.push_back(i);
	}
	//cout<<"S:";
	//for(int x:S)cout<<x<<' ';cout<<'\n';
	for(int x:S)T.upd(T.dfnl[l-x],1),T.upd(T.dfnr[l-x]+1,-1);
	for(int i=1;i<=n+1;++i)res[i]=T.qry(T.dfnl[node[i-1]]);
}
int resl[N],resr[N],res1[N],res2[N],res[N];
int fail1[N],fail2[N],fail3[N],pos1[N],pos2[N],pos3[N];
ll h1[N],h2[N],h3[N],h4[N];
int tot1,tot2,tot3;
int node1[N],node2[N],node3[N];
signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	powp[0]=1ll;
	for(int i=1;i<N;++i)powp[i]=powp[i-1]*p0%MOD;
	string A,B,P;cin>>A>>B>>P;
	int n=A.size(),m=B.size(),l=P.size();
	string a,b,p;a=rev(A),b=rev(B),p=rev(P); A=' '+A,B=' '+B,P=' '+P,a=' '+a,b=' '+b,p=' '+p;
	getFail(P,fail1),getFail(p,fail2); buildTree(l,fail1,T1),buildTree(l,fail2,T2);
	KMP(A,P,fail1,pos1,tot1,node1),KMP(a,p,fail2,pos2,tot2,node2);
	int j=1;
	for(int i=l+1;i<=n+1;++i){	// n+1?
		resl[i]=resl[i-1];
		if(pos1[j]==i-l)++resl[i],++j;
	}
	j=tot1;
	for(int i=n-l+1;i>=1;--i){
		resr[i]=resr[i+1];
		if(pos1[j]==i)++resr[i],--j;
	}
	//for(int i=1;i<=n;++i)cout<<resl[i]<<' '<<resr[i]<<'\n';
	KMP(B,P,fail3,pos3,tot3,node3); 
	for(int i=1;i<=n+1;++i)res[i]=resl[i]+resr[i]+tot3;
	getHash(P,h1),getHash(p,h2),getHash(B,h3),getHash(b,h4);
	solve1(A,B,P,fail1,h1,h3,res1,T1,node1),solve1(a,b,p,fail2,h2,h4,res2,T2,node2);
	//for(int i=1;i<=n+1;++i)cout<<res1[i]<<' '<<res2[i]<<'\n';cout<<'\n';
	for(int i=1;i<=n+1;++i)res[i]+=res1[i]+res2[n+2-i];//,cout<<res1[i]<<' '<<res2[i]<<' '<<res[i]<<'\n';
	//res[n+1]+=res1[n+1]+res2[0];
	int maxv=0,cnt=0;
	for(int i=1;i<=n+1;++i)maxv=max(maxv,res[i]);
	for(int i=1;i<=n+1;++i)cnt+=res[i]==maxv;
	vector<int> v;
	for(int i=1;i<=n+1;++i){
		if(res[i]==maxv) v.push_back(i);
	}
	cout<<maxv<<' '<<cnt<<' '<<v[0]-1<<' '<<v[v.size()-1]-1<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18400kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

ok 4 number(s): "2 2 6 7"

Test #2:

score: 0
Accepted
time: 0ms
memory: 18568kb

input:

z
zzkkzzkk
z

output:

5 2 0 1

result:

ok 4 number(s): "5 2 0 1"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 21476kb

input:

wgwwggggw
g
gggg

output:

2 2 4 8

result:

wrong answer 2nd numbers differ - expected: '5', found: '2'