# 2 条题解

• @ 2020-11-28 09:13:45
``````#include<cstdio>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=4e6+5;
const int base=29;
int ts,tt,n,m,mid;//mid=(n+m)/2,ts和tt:totals和totalt
char ch,s[maxn];//s串
multiset <unsigned long long> hashh;//存t串的multiset
unsigned long long hash_qzh[maxn],ans,work2;//前缀哈希
unsigned long long flag1=1,flag2=1;//flag1=base^n-mid,flag2=base^m
unsigned long long  dl[maxn];//去重用队列
inline void init(){//读入
scanf("%d%d%d%d",&ts,&tt,&n,&m);
mid=(n+m)>>1;
for(register int i=0;i<ts;i++){//读入s串，注意智能储存
for(register int j=i*n+1;j<=(i+1)*n;j++){
s[j]=getchar();
while(s[j]<'a' || s[j]>'z')s[j]=getchar();
}
}
for(register int i=1;i<=tt;i++){
unsigned long long hash_t=0;
for(register int j=1;j<=m;j++){
char ch=getchar();
while(ch<'a' || ch>'z')ch=getchar();
hash_t=hash_t*base+(ch-'a');
}
hashh.insert(hash_t);//存multiset
}
return ;
}
inline unsigned long long search(int l,int r,unsigned long long flag){//flag=base^(r-l+1)
return hash_qzh[r]-hash_qzh[l-1]*flag;
}
inline void workk(){//对应n>m的情况
dl[0]=0;
for(register int i=1;i<=mid;i++){
int j=i+n-mid-1;//i为头,j为末尾
if(search(i,j,flag1)==work2)//如果那一段等于work2
dl[++dl[0]]=search(j+1,j+m,flag2);//把所对应的t值放入队列
}
sort(dl+1,dl+dl[0]+1);//排个序去重
for(register int i=1;i<dl[0];i++){//在multiset中找一下
if(dl[i+1]!=dl[i]) ans+=hashh.count(dl[i]);
}
ans+=hashh.count(dl[dl[0]]);
return ;
}
inline void workk2(){//对于n=m的情况，与上面类比
dl[0]=0;
for(register int i=1;i<=mid;i++){
dl[++dl[0]]=search(i,i+m-1,flag2);
}
sort(dl+1,dl+dl[0]+1);
for(register int i=1;i<dl[0];i++){
if(dl[i+1]!=dl[i]) ans+=hashh.count(dl[i]);
}
ans+=hashh.count(dl[dl[0]]);
return ;
}
int main(){
init();
for(register int i=1;i<=n-mid;i++)
flag1*=base;
for(register int i=1;i<=m;i++)
flag2*=base;
for(register int i=0;i<ts;i++){
work2=0;//记得work2初始化(笔者也掉过这个坑
for(register int j=1;j<=mid;j++){//求hash_qzh
hash_qzh[j]=hash_qzh[j-1]*base+s[i*n+j]-'a';
}
for(register int j=1;j<=mid;j++){//求倍长部分的hash_qzh
hash_qzh[j+mid]=hash_qzh[j+mid-1]*base+s[i*n+j]-'a';
}
for(register int j=mid+1;j<=n;j++)//求work2的哈希值
work2=work2*base+s[i*n+j]-'a';
if(n>m) workk();//两种情况讨论
else workk2();
}
printf("%llu\n",ans);
return 0;
}
``````
• @ 2017-03-27 19:15:30

注意保证n>=m

将T集合的字符串hash一下存到map里记录下出现次数
然后枚举S集合每一个串，分成两部分，左边a构成一半，右边b和T集合里的某个串构成一半
然后我们要枚举a的循环旋转的各种形态去和map里的hash值碰撞，具体做法是把a复制一遍，删去最后一个字符，这样a'中每一个长度为a.len的连续子串都是a的循环等价串，然后hash一下，拿hash(a)-hash(b)*base^(a.len-b.len)的值去和map里的值碰撞统计答案即可
http://blog.leanote.com/post/okami/vijos1960

• 1

ID
1960

7

(无)

357

57

16%

2