题目链接传送门

题解:

  枚举每一行,每一行当中连续的y个我们hash 出来

  那么一行就是 m - y + 1个hash值,形成的一个新 矩阵 大小是 n*(m - y + 1), 我们要找到x*y这个矩阵的 话 是不是就是 在每一列跑kmp就行了?

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 2e3+, M = 1e3+,inf = 2e9; const ULL mod = 10000019ULL;
int n,m,x,y,T,fail[N];
char a[N][N],b[N][N];
ULL has[N][N],mp[N][N],s[N],t[N],sqr[N];
void build_fail() {
int j = ;
memset(fail,,sizeof(fail));
for(int i = ; i <= y; ++i) {
while(j&&s[i]!=s[j+]) j = fail[j];
if(s[i] == s[j+]) j++;
fail[i] = j;
}
}
int kmp() {
int ret = , j = ;
for(int i = ; i <= n; ++i) {
while(j&&s[j+]!=t[i]) j = fail[j];
if(s[j+] == t[i]) j++;
if(j == x) {
ret += ;
j = fail[j];
}
}
return ret;
}
int main() {
sqr[] = ;
for(int i = ; i < N; ++i) sqr[i] = sqr[i-] * mod;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
for(int i = ; i <= n; ++i) scanf("%s",a[i]+);
scanf("%d%d",&x,&y);
for(int i = ; i <= x; ++i) scanf("%s",b[i]+);
if(n < x || m < y) {
puts("");
continue;
}
for(int i = ; i <= n; ++i) {
for(int j = ; j <= m; ++j)
has[i][j] = has[i][j - ] * mod + a[i][j];
}
for(int i = ; i <= x; ++i) {
ULL now = , ps = ;
for(int j = ; j <= y; ++j) {
now = now * mod + b[i][j];
}
s[i] = now;
}
build_fail();
int ans = ;
for(int j = ; j <= m - y + ; ++j) {
for(int i = ; i <= n; ++i) {
int l = j, r = j + y - ;
ULL now = has[i][r] - has[i][l-] * sqr[r - l + ];
t[i] = now;
}
ans += kmp();
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. 直播时代--IOS直播客户端SDK,美颜直播【开源】
  2. TextVeiw 的 No package identifier when getting value for resource numb
  3. Java中常用的查找算法——顺序查找和二分查找
  4. [HTTP那些事]网络请求API
  5. UCOS-消息队列(学习笔记)
  6. 30天轻松学习javaweb_打包web项目成war
  7. jQuery - Chaining
  8. 游戏设计模式:Subclass Sandbox模式,以及功能方法集的设计思考
  9. hdu4630No Pain No Game (多校3)(树状数组)
  10. 如何为可扩展系统进行Java Socket编程
  11. libcurl get post http
  12. [LeetCode] 033. Search in Rotated Sorted Array (Hard) (C++)
  13. (蓝牙)网络编程中,使用InputStream read方法读取数据阻塞的解决方法
  14. Java笔记:String类
  15. 原生JS元素怎么取消事件
  16. JAVA数组和集合谁是儿子
  17. 构建SSH服务
  18. Lexicography
  19. CNN卷积层基础:特征提取+卷积核+反向传播
  20. 【RS】CoupledCF: Learning Explicit and Implicit User-item Couplings in Recommendation for Deep Collaborative Filtering-CoupledCF:在推荐系统深度协作过滤中学习显式和隐式的用户物品耦合

热门文章

  1. TOJ 4815: 关押罪犯
  2. World Finals 2017
  3. 牛腩新闻发布系统(二):SQLHelper重构(二)
  4. 机器学习实战之kNN算法
  5. 标准C程序设计七---07
  6. Poi写文件时报java.io.IOException: Read error
  7. asp.net MVC最简单的增删查改!(详)
  8. BOJ 2773 第K个与m互质的数
  9. 动态规划—最长回文子串LEETCODE第5题深度剖析
  10. Centos7 下的防火墙端口配置