fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty