fork(1) download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. #define rep(i,x,y) for(i=x;i<=y;i++)
  7. #define pb push_back
  8. #define mp make_pair
  9. #define upmin(x,y) x=min(x,y)
  10. const int L=50010,R=4,N=L*R,Q=100010,inf=int(1e9);
  11. int l,q,g,all,i,j,k,p,x,y,p1,p2,res,tot;char s[L],s0[11];
  12. int h[600000],ans[Q],d[R+1][L],tmp[N],li[N],l2[N],pos[N],num[N],vg[N],la[L],ne[L];vector<int> v[N];
  13. struct ask{int x,y,lx,ly,nn;}c[Q];
  14. bool cmp(ask a,ask b){return mp(a.x,a.y)<mp(b.x,b.y);}
  15. int ins(int x){if(h[x])return h[x];num[++tot]=x;return h[x]=tot;}
  16. int getstr(int&l0){
  17.     scanf("%s",s0+1);int i,res;l0=strlen(s0+1);
  18.     for(res=0,i=1;i<=l0;i++)res=res*27+(s0[i]-'a'+1);return res;
  19. }
  20. void calcd(int id,int l0){
  21.     int i,j,k,la0,ne0,now;
  22.     rep(j,1,R){
  23.         for(int k=0;k<=l;k++)la[k]=-inf,ne[k]=inf;
  24.         for(int k=0;k<vg[id];k++){
  25.             now=v[id][k];
  26.             la0=(k==0)?1:v[id][k-1]+1;
  27.             ne0=(k==vg[id]-1)?l:v[id][k+1]-1;
  28.             rep(i,now,ne0)la[i]=now;
  29.             rep(i,la0,now)ne[i]=now;
  30.         }
  31.         rep(i,1,l)d[j][i]=min(max(i+j,ne[i]+l0)-i,max(i+j,la[i]+l0)-la[i]);
  32.     }
  33. }
  34. int main(){
  35.     scanf("%s%d",s+1,&q);l=strlen(s+1);
  36. 	rep(i,1,l)for(res=0,j=1;j<=R&&i+j-1<=l;j++)
  37.     l2[++all]=j,v[pos[all]=ins(res=res*27+(s[i+j-1]-'a'+1))].pb(li[all]=i);
  38.     rep(i,1,tot)vg[i]=v[i].size();
  39.     rep(i,1,q){
  40.         int ida=h[getstr(p1)],idb=h[getstr(p2)];
  41.         if(ida==0||idb==0)ans[i]=-1;
  42.         else{ans[i]=inf;if(vg[ida]<vg[idb])swap(ida,ida);c[++g]=(ask){ida,idb,p1,p2,i};}
  43.     }
  44.     sort(c+1,c+1+g,cmp);
  45.     for(i=1;i<=g;i=j+1){
  46.         long long totcnt=0;
  47.         for(j=i;j<=g&&c[j].x==c[i].x;j++)totcnt+=vg[c[j].y]+vg[c[i].x];j--;
  48.         if(totcnt>all){
  49.             calcd(c[i].x,c[i].lx);    
  50.             rep(k,1,tot)tmp[k]=inf;
  51.             rep(k,1,all)upmin(tmp[pos[k]],d[l2[k]][li[k]]);
  52.             rep(k,i,j)upmin(ans[c[k].nn],tmp[c[k].y]);
  53.         }
  54.         else
  55.         rep(k,i,j)
  56.         for(p1=p2=0,x=c[k].x,y=c[k].y;p1<vg[x]&&p2<vg[y];v[x][p1]<=v[y][p2]?p1++:p2++)
  57.         upmin(ans[c[k].nn],max(v[x][p1]+c[k].lx,v[y][p2]+c[k].ly)-min(v[x][p1],v[y][p2]));
  58.     }
  59.     rep(i,1,q)printf("%d\n",ans[i]);
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 16488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HB544x
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!