题意：给出一个n*m的字符矩阵T，你的任务是找出给定的x*y的字符矩阵P出现了多少次，即需要在二维文本串T中查找二维模式串P。
思路：这题的最优解应该是hash，不过就当给自动机练练手了，先将P的每一行字符串建立自动机，然后再将T中的每一行字符串去匹配，用一个ans[ r ][ c ]表示T中以(r,c)为左上角，与P等大的矩形中有多少行字符串是完全等同于P的，这样ans[ r ][ c ]==x时答案数量就加一，当T中第 i 行字符串第 j 个字符在字典树第u个节点有匹配，那么ans[ i-val[u] ][ j ]++。要十分注意的是，建自动机时有可能许多字符串是一样的，所以val数组要用vector记录节点的状态。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e4+100;
const int size=65;
int ans[1005][1005],sum;
int n,m,x,y;
struct AC
{
int ch[maxn][size];
vector<int>val[maxn]; //有可能多个字符串是一样的
int f[maxn];
int last[maxn];
int sz;
void clear()
{
memset(ch[0],0,sizeof(ch[0]));
val[0].clear();
sz=1;
}
int index(char c)
{
if(c>='0'&&c<='9')
return c-'0';
if(c>='a'&&c<='z')
return c-'a'+10;
return c-'A'+36;
}
void insert(char *s,int v)
{
int u=0,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=index(s[i]);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz].clear();
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u].push_back(v);
}
void print(int k,int i,int j)
{
if(j)
{
for(int p=0;p<val[j].size();p++)
{
int t=val[j][p];
if(k>=t) // k<t时肯定无解
{
ans[k-t][i]++;
if(ans[k-t][i]==x)
sum++;
}
}
print(k,i,last[j]);
}
}
void find(char *T,int k)
{
int len=strlen(T);
int j=0;
for(int i=0;i<len;i++)
{
int c=index(T[i]);
while(j&&!ch[j][c])j=f[j];
j=ch[j][c];
if(val[j].size()!=0)print(k,i,j);
else if(last[j])print(k,i,last[j]);
}
}
void getfail()
{
int u=0;
queue<int>q;
f[0]=last[0]=0;
for(int i=0;i<size;i++)
if(ch[u][i])
{
f[ch[u][i]]=last[ch[u][i]]=0;
q.push(ch[u][i]);
}
while(!q.empty())
{
int r=q.front();q.pop();
for(int c=0;c<size;c++)
{
int u=ch[r][c];
if(!u)continue;
q.push(u);
int v=f[r];
while(v&&!ch[v][c])v=f[v];
f[u]=ch[v][c];
last[u]=val[f[u]].size()?f[u]:last[f[u]];
}
}
}
}a;
char S[1005][1005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i;
char str[105];
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%s",S[i]);
memset(ans[i],0,sizeof(ans[i]));
}
scanf("%d%d",&x,&y);
a.clear();
for(i=0;i<x;i++)
{
scanf("%s",str);
a.insert(str,i+1);
}
a.getfail();
sum=0;
for(i=0;i<n;i++)
a.find(S[i],i+1);
printf("%d\n",sum);
}
}