题解

首先题中说了$n>=m$;
分成的循环串左右两边为本质相同的单循环串循环串，分别长为$l = \frac{n + m}{2} $;
所以$S$串的前$l$位为双循环串的一半$S1$，后一半为$S2$;
倍长$S1$找到$S2$在$S1$中出现的位置，把单循环串匹配位置后的剩下的$m$位哈希存下来；
读入每个$T$串查找即可
注意有可能$S2$在$S1$中会重复出现，记录$last$防止重复计算；

 #include<bits/stdc++.h>

 #define ull unsigned long long

 #define base 1234567891

 #define il inline

 #define rg register

 using namespace std;

 const int N=,sz=1e7;

 int n,m,k,l,t1,t2,o,nt[sz],hd[sz],w[sz],nxt[N<<],lst[sz];

 char s[N<<],t[N<<];

 ull h[N<<],v[sz],pw,ans;

 il char gc(){

     static char*p1,*p2,buf[];

     if(p1==p2)p2=(p1=buf)+fread(buf,,,stdin);

     return(p1==p2)?EOF:*p1++;

 }

 il int rd(){

     int x=; char c=gc();

     while(c<''||c>'')c=gc();

     while(c>=''&&c<='')x=x*+c-'',c=gc();

     return x;

 }

 il char gt(){char c=gc();while(!isalpha(c))c=gc();return c;}

 void solve(){

     for(rg int i=;i<=n;i++){

         for(rg int j=;j<=l;j++)h[j]=h[j-]*base+(s[j]=gt());

         for(rg int j=;j<=l;j++)h[j+l]=h[j+l-]*base+s[j];

         if(t1)t[]=gt();

         for(rg int j=,tj=;j<=t1;nxt[++j]=tj){

             t[j]=gt();

             while(tj&&t[j]!=t[tj+])tj=nxt[tj];

             if(t[j]==t[tj+])tj++;

         }

         for(rg int j=,tj=;j<=l+max(,t1-);j++){

             while(tj&&s[j]!=t[tj+])tj=nxt[tj];

             if(s[j]==t[tj+])tj++;

             if(!t1||tj==t1){

                 ull x = h[j+t2] - h[j]*pw;

                 int fg=;

                 for(int r=hd[x%sz];r;r=nt[r])if(v[r]==x){

                     fg=;

                     if(lst[r]!=i)w[r]++,lst[r]=i;

                     break;

                 }

                 if(!fg)nt[++o]=hd[x%sz],v[hd[x%sz]=o]=x,w[o]=,lst[o]=i;

                 tj=nxt[tj];

             }

         }

     }

     t1-=l;

     for(rg int i=;i<=m;i++){

         ull x=;for(rg int j=;j<=t2;j++)x=x*base+gt();

         for(int r=hd[x%sz];r;r=nt[r])if(v[r]==x){ans+=w[r];break;}

     }

 }

 int main(){

     #ifndef ONLINE_JUDGE

     freopen("bzoj4084.in","r",stdin);

     freopen("bzoj4084.out","w",stdout);

     #endif

     n=rd();m=rd();t1=rd();t2=rd();l=(t1+t2)>>;

     t1-=l;for(int i=pw=;i<=t2;i++)pw=pw*base;

     solve();

     printf("%llu\n",ans);

     return ;

 }

bzoj4084

巴特西

【bzoj4084】【sdoi2015】双旋转字符串

题解

最新文章

热门文章