QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#537462 | #5256. Insertions | RockyYue | WA | 0ms | 21476kb | C++14 | 3.4kb | 2024-08-30 13:57:11 | 2024-08-30 13:57:11 |
Judging History
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'