• 題解

  • 首先題中說了$n>=m$;
  • 分成的循環串左右兩邊為本質相同的單循環串循環串，分別長為$l = \frac{n + m}{2} $;
  • 所以$S$串的前$l$位為雙循環串的一半$S1$，后一半為$S2$;
  • 倍長$S1$找到$S2$在$S1$中出現的位置，把單循環串匹配位置后的剩下的$m$位哈希存下來；
  • 讀入每個$T$串查找即可
  • 注意有可能$S2$在$S1$中會重復出現，記錄$last$防止重復計算；
  • 1 #include<bits/stdc++.h> 2 #define ull unsigned long long 3 #define base 1234567891 4 #define il inline 5 #define rg register 6 using namespace std; 7 const int N=8000010,sz=1e7; 8 int n,m,k,l,t1,t2,o,nt[sz],hd[sz],w[sz],nxt[N<<1],lst[sz]; 9 char s[N<<1],t[N<<1]; 10 ull h[N<<1],v[sz],pw,ans; 11 il char gc(){ 12 static char*p1,*p2,buf[1000000]; 13 if(p1==p2)p2=(p1=buf)+fread(buf,1,1000000,stdin); 14 return(p1==p2)?EOF:*p1++; 15 } 16 il int rd(){ 17 int x=0; char c=gc(); 18 while(c<'0'||c>'9')c=gc(); 19 while(c>='0'&&c<='9')x=x*10+c-'0',c=gc(); 20 return x; 21 } 22 il char gt(){char c=gc();while(!isalpha(c))c=gc();return c;} 23 void solve(){ 24 for(rg int i=1;i<=n;i++){ 25 for(rg int j=1;j<=l;j++)h[j]=h[j-1]*base+(s[j]=gt()); 26 for(rg int j=1;j<=l;j++)h[j+l]=h[j+l-1]*base+s[j]; 27 if(t1)t[1]=gt(); 28 for(rg int j=2,tj=0;j<=t1;nxt[++j]=tj){ 29 t[j]=gt(); 30 while(tj&&t[j]!=t[tj+1])tj=nxt[tj]; 31 if(t[j]==t[tj+1])tj++; 32 } 33 for(rg int j=1,tj=0;j<=l+max(0,t1-1);j++){ 34 while(tj&&s[j]!=t[tj+1])tj=nxt[tj]; 35 if(s[j]==t[tj+1])tj++; 36 if(!t1||tj==t1){ 37 ull x = h[j+t2] - h[j]*pw; 38 int fg=0; 39 for(int r=hd[x%sz];r;r=nt[r])if(v[r]==x){ 40 fg=1; 41 if(lst[r]!=i)w[r]++,lst[r]=i; 42 break; 43 } 44 if(!fg)nt[++o]=hd[x%sz],v[hd[x%sz]=o]=x,w[o]=1,lst[o]=i; 45 tj=nxt[tj]; 46 } 47 } 48 } 49 t1-=l; 50 for(rg int i=1;i<=m;i++){ 51 ull x=0;for(rg int j=1;j<=t2;j++)x=x*base+gt(); 52 for(int r=hd[x%sz];r;r=nt[r])if(v[r]==x){ans+=w[r];break;} 53 } 54 } 55 int main(){ 56 #ifndef ONLINE_JUDGE 57 freopen("bzoj4084.in","r",stdin); 58 freopen("bzoj4084.out","w",stdout); 59 #endif 60 n=rd();m=rd();t1=rd();t2=rd();l=(t1+t2)>>1; 61 t1-=l;for(int i=pw=1;i<=t2;i++)pw=pw*base; 62 solve(); 63 printf("%llu\n",ans); 64 return 0; 65 } bzoj4084

    ?

轉載于:https://www.cnblogs.com/Paul-Guderian/p/10241620.html

總結

以上是生活随笔為你收集整理的【bzoj4084】【sdoi2015】双旋转字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。