Description
Given an N × M matrix, your task is to find the number of occurences of an X × Y pattern.
Input
The first line contains a single integer t (t ≤ 15), the number of test cases.
For each case, the first line contains two integers N and M (N, M ≤ 1000). The next N lines
contain M characters each.
The next line contains two integers X and Y (X, Y ≤ 100). The next X lines contain Y characters
each.Output
For each case, output a single integer in its own line, the number of occurrences.
Sample Input
2
1 1
x
1 1
y
3 3
abc
bcd
cde
2 2
bc
cd
Sample Output
0
2
【题意】
在二维文本串T中查找一个二维模板串P出现了多少次。
【分析】
拆分模板串P的每一行，建AC自动机。
拆分文本串T的每一行，在自动机中与P匹配，ct[i][j]表示以点(i,j)为左上角、与P等大的矩形有多少个对应的行与P匹配。
最后ct[i][j]==P的行数的i，j就是一个匹配点，ans++。
注意：1.原本我在trie的叶子用动态数组维护了一个表示这一行是P的第几行的数组，但是超时了，后来看了LRJ的代码，改成了用一个nt[i]来表示重复的行的下一行，就A了。
2.注意在ct[i][j]里加的时候判断i,j是否大于0.
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define Maxl 110
#define INF 0xfffffff int n,m,l,r;
int ct[Maxn][Maxn],nt[Maxl];
char s[Maxn][Maxn];
char ss[Maxn]; struct node
{
int fail,mark;
int son[];
}t[Maxn*Maxn];int tot; void upd(int x)
{
t[x].mark=;
memset(t[x].son,,sizeof(t[x].son));
} void read_trie(int tk)
{
scanf("%s",s[]+);
int len=strlen(s[]+);
for(int i=;i<=len;i++) ss[i]=s[][len-i+];
int now=;
for(int i=;i<=len;i++)
{
int ind=ss[i]-'a'+;
if(!t[now].son[ind])
{
t[now].son[ind]=++tot;
upd(tot);
}
now=t[now].son[ind];
if(i==len)
{
if(t[now].mark) nt[tk]=t[now].mark;//我好搞笑
t[now].mark=tk;
}
}
} queue<int > q;
void build_AC()
{
while(!q.empty()) q.pop();
q.push();
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=;i<=;i++)
{
if(t[x].son[i])
{
t[t[x].son[i]].fail=x?t[t[x].fail].son[i]:;
q.push(t[x].son[i]);
}
else t[x].son[i]=t[t[x].fail].son[i];
}
if(t[t[x].fail].mark) t[x].mark=t[t[x].fail].mark;
}
} void add(int x,int y,int z)
{
if(x-z+>=) ct[x-z+][y]++;
if(nt[z]!=) add(x,y,nt[z]);
} void ffind()
{
int now;
memset(ct,,sizeof(ct));
for(int i=;i<=n;i++)
{
now=;
for(int j=m;j>=;j--)
{
now=t[now].son[s[i][j]-'a'+];
if(t[now].mark) add(i,j,t[now].mark);
}
}
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(ct[i][j]==l) ans++;
printf("%d\n",ans);
} void init()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%s",s[i]+);
tot=;upd();
scanf("%d%d",&l,&r);
memset(nt,,sizeof(nt));
for(int i=;i<=l;i++)
{
read_trie(i);
}
build_AC();
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
ffind();
}
return ;
}
[UVA11019]
2016-07-12 15:37:53