QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89086 | #5256. Insertions | tricyzhkx | WA | 4ms | 13024kb | C++14 | 3.2kb | 2023-03-18 20:22:59 | 2023-03-18 20:23:02 |
Judging History
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'