#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
int c[][];
int mx,nx,m,n;
struct AC
{
int ch[][];
int cnt;
int value[],fail[],last[],next[];
AC(){memset(next,,sizeof(next));memset(ch,,sizeof(ch));cnt=;memset(value,,sizeof(value));memset(fail,,sizeof(fail));memset(last,,sizeof(last));}
void trie(char *s,int v)
{
int now=,len=strlen(s);
for(int i=;i<len;i++)
{
if(!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++cnt;
now=ch[now][s[i]-'a'];
}
if(value[now])
{
next[v]=value[now];
}
value[now]=v;
}
void getfail()
{
queue<int>q;
for(int i=;i<;i++){if(ch[][i]) q.push(ch[][i]);}
while(!q.empty())
{
int now=q.front();q.pop();
for(int i=;i<;i++)
{
int u=ch[now][i];
if(!u){ch[now][i]=ch[fail[now]][i];continue;}
int t=fail[now];
while(t&&!ch[t][i]) t=fail[t];
fail[u]=ch[t][i];
last[u]=value[fail[u]]?fail[u]:last[fail[u]];
q.push(u);
}
}
}
void add(int now,int h,int i)
{
if(now)
{
if(h-value[now]+>=) c[h-value[now]+][i]++;
int t=value[now];
while(next[t])
{
t=next[t];
if(h-t+>=) c[h-t+][i]++;
}
add(last[now],h,i);
}
}
void find(char *s,int h)
{
int len=strlen(s);
int now=;
for(int i=;i<len;i++)
{
now=ch[now][s[i]-'a'];
if(value[now]) add(now,h,i);
else add(last[now],h,i);
}
}
}ac;
int main()
{
int ans=;
char chh[][];
scanf("%d%d",&mx,&nx);
for(int i=;i<mx;i++)scanf("%s",chh[i]);
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
{
char temp[];
scanf("%s",temp);
ac.trie(temp,i);
}
ac.getfail();
for(int i=;i<mx;i++) ac.find(chh[i],i);
for(int i=;i<mx;i++)
for(int j=;j<nx;j++) if(c[i][j]==m) ans++;
cout<<ans;
}
矩阵匹配器D316
难度级别:C; 运行时间限制:1500ms; 运行空间限制:262144KB; 代码长度限制:2000000B
试题描述
给你一个sx*sy的小矩阵和一个mx*my的大矩阵,请你求出小矩阵在大矩阵中出现的次数
输入
第一行两个正整数mx,my
接下来跟一个mx行my列的大矩阵
又接下来两个正整数sx,sy
再接下来跟一个sx行sy列的小矩阵
输出
小矩阵在大矩阵中出现的次数
输入示例
3 3
abc
bca
caa
2 2
bc
ca
输出示例
2
其他说明
数据范围:sx≤mx≤1000,sy≤my≤1000 sx,sy≤100

最新文章

  1. 正则化方法:L1和L2 regularization、数据集扩增、dropout
  2. Linux架构
  3. msvc库没有安装包,编译选项选择 代码生成 MT【多线程】,C#调用
  4. iOS监听电话事件
  5. React Native学习(四)—— 写一个公用组件(头部)
  6. Struts2 之 Action 类访问 WEB 资源
  7. bat脚本自定义魔兽warIII运行分辨率,去黑边
  8. Vue diff 算法
  9. CLOS架构是啥?
  10. python 内置函数enumerate()
  11. 【leetcode】278. First Bad Version
  12. 题解 P2920 【[USACO08NOV]时间管理Time Management】
  13. python标准库介绍——35 pipes 模块详解
  14. k8s集群搭建指南
  15. Taffy自动化测试框架Web开发,Python Flask实践详解
  16. pcap的安装与配置
  17. 洛谷 P1231 教辅的组成(网络最大流+拆点加源加汇)
  18. numpy 的三角函数运算
  19. 将ojdbc 添加到maven
  20. CSS 2D转换

热门文章

  1. Windows下zookeeper注册中心的安装和启动
  2. 【转】android makefile文件分析
  3. js常用框架
  4. 为什么要搞vim
  5. iOS笔记056 - UI总结02
  6. CTF python沙箱逃逸进阶题目
  7. 【转载】全面解析Unity3D自动生成的脚本工程文件
  8. vue零碎收集
  9. disable-network-config
  10. 通过nbviwer在线分享python notebook