#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;
}

注意保证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