Matrix Matcher UVA - 11019AC_自动机 + 代价提前计算
2024-08-28 14:34:58
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;
}
最新文章
- vim正则表达式~转
- yum安装nginx
- Scrum领取任务
- Duilib实现类似电脑管家扫描目录效果
- table的css样式
- iis7下iis安全狗不能用怎么办(安装iis6兼容性)
- Sql 行转列问题总结
- MVC之超链接的寻址
- [转载]实战Linux下VMware虚拟机根目录空间扩充
- 简单的ajax获取json
- Hibernate:如何映射聚合?
- [UIKit学习]02.关于UIButton
- python中的turtle库绘制图形
- [数据结构] 用C语言模拟一个简单的队列程序
- 安装连接mysql8时候遇到的问题以及解决(转)
- 【C#】简单的发送socket字符串
- Landen邀请码
- 网友写的解决uniGUI限制的方法
- 分享七个绚丽夺目的JQuery导航(还有苹果、猪八戒等),有图有真相
- am335x ti SDK6.0 kernel 时钟源码文件记录