QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89086#5256. InsertionstricyzhkxWA 4ms13024kbC++143.2kb2023-03-18 20:22:592023-03-18 20:23:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-18 20:23:02]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:13024kb
  • [2023-03-18 20:22:59]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
int nxt1[100010],nxt2[100010],nxt3[100010],a[100010],b[100010],dfn1[100010],dfn2[100010],sz1[100010],sz2[100010],f[100010],ans[100010],tot;
vector<int> G1[100010],G2[100010];
vector<pair<int,int>> U[100010],Q[100010];
char S[100010],T[100010],P[100010];
void KMP(char *s,int n,int *nxt)
{
	for(int i=2,j=0;i<=n;i++)
	{
		for(;j && s[i]!=s[j+1];j=nxt[j]);
		if(s[i]==s[j+1]) j++;
		nxt[i]=j;
	}
}
void dfs1(int u){dfn1[u]=++tot;for(int v:G1[u]) dfs1(v);}
void dfs2(int u){dfn2[u]=++tot;for(int v:G2[u]) dfs2(v);}
struct BIT
{
	int n,s[100010];
	void update(int x,int y){for(int i=x;i<=n;i+=i&(-i)) s[i]+=y;}
	int query(int x)
	{
		int ans=0;
		for(int i=x;i;i-=i&(-i)) ans+=s[i];
		return ans;
	}
}B;
void update(int u,int x){B.update(dfn2[u],x);B.update(dfn2[u]+sz2[u],-x);}
int main()
{
	int n,m,K;
	scanf("%s%s%s",S+1,T+1,P+1);
	n=strlen(S+1);m=strlen(T+1);K=strlen(P+1);
	reverse(P+1,P+K+1);KMP(P,K,nxt2);
	reverse(P+1,P+K+1);KMP(P,K,nxt1);
	reverse(nxt2+1,nxt2+K+1);
	for(int i=1;i<=K;i++) nxt2[i]=K-nxt2[i]+1;
	int u=K+1,c=0;
	for(int i=m;i>=1;i--)
	{
		for(;u<=K && T[i]!=P[u-1];u=nxt2[u]);
		if(T[i]==P[u-1]) u--;
	}
	for(;u<=K;u=nxt2[u]) f[u-1]++;
	f[0]=0;
	for(int i=1;i<=K;i++) f[i]+=f[nxt1[i]];
	for(int i=1,j=0;i<=n;i++)
	{
		for(;j && S[i]!=P[j+1];j=nxt1[j]);
		if(S[i]==P[j+1]) j++;
		a[i]=j;ans[i]+=f[j];
	}
	memset(f+1,0,sizeof(int)*K);u=0;
	for(int i=1;i<=m;i++)
	{
		for(;u && T[i]!=P[u+1];u=nxt1[u]);
		if(T[i]==P[u+1]) u++;
	}
	for(;u;u=nxt1[u]) f[u+1]++;
	f[K+1]=0;
	for(int i=K;i>=1;i--) f[i]+=f[nxt2[i]];
	b[n+1]=K+1;
	for(int i=n,j=K+1;i>=1;i--)
	{
		for(;j<=K && S[i]!=P[j-1];j=nxt2[j]);
		if(S[i]==P[j-1]) j--;
		b[i]=j;ans[i-1]+=f[j];
	}
	memset(f+1,0,sizeof(int)*K);
	for(int i=1,j=0,cnt=0;i<=n;i++)
	{
		for(;j && S[i]!=P[j+1];j=nxt1[j]);
		if(S[i]==P[j+1]) j++;
		if(j==K) cnt++,j=nxt1[j];
		ans[i]+=cnt;
	}
	for(int i=n,j=K+1,cnt=0;i>=1;i--)
	{
		for(;j<=K && S[i]!=P[j-1];j=nxt2[j]);
		if(S[i]==P[j-1]) j--;
		if(j==1) cnt++,j=nxt2[j];
		ans[i-1]+=cnt;
	}
	for(int i=1,j=0;i<=m;i++)
	{
		for(;j && T[i]!=P[j+1];j=nxt1[j]);
		if(T[i]==P[j+1]) j++;
		if(j==K) c++,j=nxt1[j];
	}
	for(int i=0;i<=n;i++) ans[i]+=c;
	if(m<K)
	{
		for(int i=1;i<=K;i++) G1[nxt1[i]].push_back(i),G2[nxt2[i]].push_back(i);
		dfs1(0);tot=0;dfs2(K+1);
		fill(sz1,sz1+K+1,1);fill(sz2+1,sz2+K+2,1);
		for(int i=K;i>=1;i--) sz1[nxt1[i]]+=sz1[i];
		for(int i=1;i<=K;i++) sz2[nxt2[i]]+=sz2[i];
		KMP(T,m,nxt3);
		for(int i=1,j=0;i<=K;i++)
		{
			for(;j && P[i]!=T[j+1];j=nxt3[j]);
			if(P[i]==T[j+1]) j++;
			if(j==m)
			{
				if(i>m && i<K)
				{
					U[dfn1[i-m]].emplace_back(i+1,1);
					U[dfn1[i-m]+sz1[i-m]].emplace_back(i+1,-1);
				}
				j=nxt3[j];
			}
		}
		for(int i=0;i<=K;i++) Q[dfn1[a[i]]].emplace_back(dfn2[b[i+1]],i);
		B.n=K;
		for(int i=1;i<=K;i++)
		{
			for(auto p:U[i]) update(p.first,p.second);
			for(auto p:Q[i]) ans[p.second]+=B.query(p.first);
		}
	}
	int aans=0,cnt=0,mn=1e9,mx=0;
	for(int i=0;i<=n;i++) aans=max(aans,ans[i]);
	for(int i=0;i<=n;i++)
		if(ans[i]==aans) cnt++,mn=min(mn,i),mx=max(mx,i);
	cout<<aans<<" "<<cnt<<" "<<mn<<" "<<mx<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 12864kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

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

Test #2:

score: 0
Accepted
time: 3ms
memory: 12996kb

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: 4ms
memory: 13024kb

input:

wgwwggggw
g
gggg

output:

2 2 4 8

result:

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