using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; using static Rh; static class Program{ const int mod=(int)1e9+7; static void Main(){ Sc sc=new Sc(); var s=sc.S; var t=sc.S; Rh rh=new Rh(); var hs=new Hsa(s); var ht=t; int ans=0; for(int i = t.Length-1;iRh.n){ Rh.n=n; r1=new long[n+1]; r2=new long[n+1]; r1[0]=r2[0]=1; hs=new Hs[n+1]; hs[0]=new Hs(0); for(int i = 1;i<=n;i++) { r1[i]=(r1[i-1]*b1)%mod1; r2[i]=(r2[i-1]*b2)%mod2; hs[i]=hs[i-1]+a[i-1]; } } else{ hs=new Hs[n+1]; hs[0]=new Hs(0); for(int i = 1;i<=n;i++) {hs[i]=hs[i-1]+a[i-1];} } } public Hsa(string a){ n=a.Length; if(n>Rh.n){ Rh.n=n; r1=new long[n+1]; r2=new long[n+1]; r1[0]=r2[0]=1; hs=new Hs[n+1]; hs[0]=new Hs(0); for(int i = 1;i<=n;i++) { r1[i]=(r1[i-1]*b1)%mod1; r2[i]=(r2[i-1]*b2)%mod2; hs[i]=hs[i-1]+a[i-1]; } } else{ hs=new Hs[n+1]; hs[0]=new Hs(0); for(int i = 1;i<=n;i++) {hs[i]=hs[i-1]+a[i-1];} } } public static implicit operator Hsa(int[] a){return new Hsa(a);} public static implicit operator Hsa(string a){return new Hsa(a);} public Hs Get(int a,int b){return hs[b+1]-hs[a];} public int Bs(int a,int b){return Bs(a,b,n-Max(a,b));} public int Bs(int a,int b,int ub){ int lb=-1,mid=0; while(ub-lb>1){ mid=(ub+lb)/2; if(Get(a,a+mid)!=Get(b,b+mid)){ub=mid;} else{lb=mid;} } return ub; } public int Bsp(Hsa a){return Bsp(0,a);} public int Bsp(int k,Hsa a){ int lb=-1,mid=0,ub=Min(n-k,a.n); while(ub-lb>1){ mid=(ub+lb)/2; if(Get(k,mid+k)!=a.Get(0,mid)){ub=mid;} else{lb=mid;} } return ub; } public int Bss(Hsa a){return Bss(n-1,a);} public int Bss(int k,Hsa a){ int lb=0,mid=0,ub=Min(k+1,a.n)+1; while(ub-lb>1){ mid=(ub+lb)/2; if(Get(k+1-mid,k)!=a.Get(a.n-mid,a.n-1)){ub=mid;} else{lb=mid;} } return lb; } } public struct Hs{ public long h1,h2; public int d; public Hs(int n){h1=h2=d=0;} public static implicit operator bool(Hs h){return h.d>0;} public static implicit operator Hs(string s){ Hs h=new Hs(0); for(int i=0;i[] da; public Hss(string[] s){ n=s.Length; da=new Tuple[n]; for(int i = 0;iu.Item1.h1.CompareTo(v.Item1.h1)); } public int Eq(Hs h){ int lb=-1,mid=0,ub=n-1; while(ub-lb>1){ mid=(ub+lb)/2; if(da[mid].Item1.h1>=h.h1){ub=mid;} else{lb=mid;} } for(int i = ub;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i