BZOJ4048 SDOI015 双旋转字符串 Hash-白红宇

BZOJ4048 SDOI015 双旋转字符串 Hash

阅读量：4480 次

发布时间：2019-06-08

本文共 984 字，大约阅读时间需要 3 分钟。

题意：给定两个字符串集合S T，每个集合内的所有字符串长度均相同，求有多少对字符串<S_i,T_j>使得两个字符串拼接后，左右两半满足双旋转性质（一个字符串按照任意一个位置旋转后与另一个字符串重合）

题解：把较小的集合Hash后，暴力枚举另一个集合内的字符串。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;#define ll long long#define Base 233const int MAXN=4000000+2;int N,M,TS,TT;ll Hash,f[MAXN],p[MAXN],Ans;string S[MAXN],T[MAXN];map
            
              m;ll Calc(int x,int y){ if(x>y) return 0; return f[y]-f[x-1]*p[y-x+1];}int main(){ cin >> TS >> TT >> N >> M; if(TS
             
              > S[i]; for(int i=1;i<=TT;i++) cin >> T[i]; } else{ for(int i=1;i<=TS;i++) cin >> T[i]; for(int i=1;i<=TT;i++) cin >> S[i]; swap(N,M),swap(TS,TT); } p[0]=1; for(int i=1;i<=N+M;i++) p[i]=p[i-1]*Base; for(int i=1;i<=TS;i++){ for(int j=0;j
              
               >1;i<=TT;i++,Hash=0){ for(int j=0;j<2*Mid;j++) f[j+1]=f[j]*Base+T[i][j%Mid]-'a'+1; for(int j=Mid;j

View Code

转载于:https://www.cnblogs.com/WDZRMPCBIT/p/6616597.html

你可能感兴趣的文章