Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=103;
const int maxd=1005;
const int maxc=maxd*10;
const int sigma=28;
char A[maxd][maxd],B[maxn];
int ans[maxd][maxd];
int N,M,X,Y;
# define pb push_back
struct AC{
int ch[maxc][50],f[maxc];
vector<int>G[maxc];
queue<int>Q;
int cnt=0;
int idx(char t){return t-'a';}
void init(){
memset(ch,0,sizeof(ch));
memset(f,0,sizeof(f));
memset(ans,0,sizeof(ans));
for(int i=0;i<maxc;++i)G[i].clear();
cnt=0;
}
void insert(char T[],int u){
int n=strlen(T);
int j=0;
for(int i=0;i<n;++i){
int a=idx(T[i]);
if(!ch[j][a])ch[j][a]=++cnt;
j=ch[j][a];
}
G[j].pb(u);
}
void getfail(){
for(int i=0;i<=sigma;++i)if(ch[0][i]){Q.push(ch[0][i]);}
while(!Q.empty()){
int r=Q.front();Q.pop();
for(int i=0;i<=sigma;++i){
int u=ch[r][i];
if(!u){ch[r][i]=ch[f[r]][i];continue;}
Q.push(u);
int v=f[r];
f[u]=ch[v][i];
}
}
}
void operate()
{
for(int i=0;i<N;++i)
{
int p=0;
for(int j=0;j<M;++j){
int c=idx(A[i][j]);
p=ch[p][c];
int sz=G[p].size();
if(sz>0)
{
for(int g=0;g<sz;++g)
{
int h=G[p][g];
if(h<=i)ans[i-h][j-Y+1]+=1;
}
}
}
}
}
}op;
int main(){
int T;scanf("%d",&T);
while(T--){
op.init();
scanf("%d%d",&N,&M);
for(int i=0;i<N;++i)scanf("%s",A[i]);
scanf("%d%d",&X,&Y);
for(int i=0;i<X;++i){scanf("%s",B);op.insert(B,i);}
op.getfail();
op.operate();
int fin=0;
for(int i=0;i<N;++i)
for(int j=0;j<M;++j)
if(ans[i][j]==X)++fin;
printf("%d\n",fin);
}
return 0;
}

  

最新文章

  1. vim正则表达式~转
  2. yum安装nginx
  3. Scrum领取任务
  4. Duilib实现类似电脑管家扫描目录效果
  5. table的css样式
  6. iis7下iis安全狗不能用怎么办(安装iis6兼容性)
  7. Sql 行转列问题总结
  8. MVC之超链接的寻址
  9. [转载]实战Linux下VMware虚拟机根目录空间扩充
  10. 简单的ajax获取json
  11. Hibernate:如何映射聚合?
  12. [UIKit学习]02.关于UIButton
  13. python中的turtle库绘制图形
  14. [数据结构] 用C语言模拟一个简单的队列程序
  15. 安装连接mysql8时候遇到的问题以及解决(转)
  16. 【C#】简单的发送socket字符串
  17. Landen邀请码
  18. 网友写的解决uniGUI限制的方法
  19. 分享七个绚丽夺目的JQuery导航(还有苹果、猪八戒等),有图有真相
  20. am335x ti SDK6.0 kernel 时钟源码文件记录

热门文章

  1. sql语句学习(NOT EXISTS 和 NOT IN )
  2. (31)Spring Boot导入XML配置【从零开始学Spring Boot】
  3. redhat超级用户密码破解
  4. 洛谷 P1768 天路
  5. AlterDialog 经常使用的样式
  6. android高速上手(二)android开发环境搭建及hello world
  7. [NodeJS]使用Node.js写一个简单的在线聊天室
  8. springmvc and maven
  9. luogu1445 [violet]樱花 阶乘分解
  10. Linux下开启vim高亮