【题意】

给出一个n*m的字母矩阵T和一个x*y的字母矩阵S。求S在T中出现了多少次？

【解题方法】

具体见白书218页，前面写的AC 自动机，都是没有加last优化的，但是我写这个题的时候，发现不加last巨难写，好吧我太菜了。所以我选择了这种last优化（好像并没有优化？）的版本，作为AC自动机的第二种板子，方便以后遇到较难的题的处理，这样要方便一些。

将S的每行看做一个串插入ac自动机。用T的每一行去匹配。那么我们可以得到每一次匹配都匹配了S的哪些行的串以及在T的这一行的哪个位置匹配到这个S的串。我们用f[i][j]表示以(i,j)为左上角的T，匹配了S的多少行。设某一次T的第r行匹配了S的第i行，位置是[c,c+y-1]，那么令f[r-i][c]++。最后f[i][j]=x的就是能够完整匹配S的位置。

【AC 代码】参考Liurtujia的代码仓库。

//
//UVA 11019 带last 版本
//Created by just_sort 2016/8/20
//All Rights Reserved
//
#include <map>
#include <queue>
#include <cstring>
#include <string>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxnode = 100010;
const int maxs = 26;
void process_match(int pos,int v);
struct acautomata{
    int nxt[maxnode][maxs],fail[maxnode],val[maxnode],last[maxnode],sz;
    void init(){
        sz = 1;
        memset(nxt[0],0,sizeof(nxt[0]));
    }
    int newnode(){
        memset(nxt[sz],0,sizeof(nxt[sz]));
        val[sz]=0;
        return sz++;
    }
    int idx(int c){return c-'a';}
    void insert(char *s,int v){
        int u=0,n=strlen(s);
        for(int i=0; i<n; i++){
            int c=idx(s[i]);
            if(!nxt[u][c]){
                nxt[u][c]=newnode();
            }
            u=nxt[u][c];
        }
        val[u]=v;
    }
    void report(int pos,int j){//递归打印以节点j结尾的所有字符串
        if(j){
            process_match(pos,val[j]);
            report(pos,last[j]);
        }
    }
    void Find(char *T){
        int n=strlen(T),j=0;
        for(int i=0; i<n; i++){
            int c=idx(T[i]);
            j=nxt[j][c];
            if(val[j]) report(i,j);
            else if(last[j]) report(i,last[j]);
        }
    }
    void build()
    {
        queue<int>q;fail[0]=0;
        for(int i=0; i<maxs; i++){
            int u=nxt[0][i];
            if(u){fail[u]=0;last[u]=0;q.push(u);}
        }
        while(q.size()){
            int r=q.front();q.pop();
            for(int i=0; i<maxs; i++){
                int u=nxt[r][i];
                if(!u){
                    nxt[r][i]=nxt[fail[r]][i];
                    continue;
                }
                q.push(u);
                int v=fail[r];
                while(v&&!nxt[v][i]) v=fail[v];
                fail[u]=nxt[v][i];
                last[u] = val[fail[u]]?fail[u]:last[fail[u]];
            }
        }
    }
}ac;
const int maxn = 1010;
const int maxm = 1010;
const int maxx = 110;
const int maxy = 110;
char text[maxn][maxn],P[maxn][maxn];
int repr[maxn]; //repr[i]为模板第i行的代表元
int nex[maxn]; //nex[i]为模板中与第i行相等的下一行的编号
int len[maxn]; //模板各行的长度
int tr; //当前文本行编号
int cnt[maxn][maxm];//记录答案
void process_match(int pos,int v)// AC自动机每找到一个匹配会调用一次,结束位置为pos，val为v
{
    int pr = repr[v-1];//匹配到的模板行编号
    int c  = pos -len[pr]+1;//匹配到的模板列编号
    while(pr>=0){
        if(tr>=pr){
            cnt[tr-pr][c]++;
        }
        pr=nex[pr];
    }
}

int main()
{
    int T,n,m,x,y;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) scanf("%s",text[i]);
        ac.init();
        scanf("%d%d",&x,&y);
        for(int i=0; i<x; i++){
            scanf("%s",P[i]);
            len[i] = strlen(P[i]);
            repr[i] = i;
            nex[i] = -1;
            for(int j=0; j<i; j++){
                if(strcmp(P[i],P[j])==0){
                    repr[i] = j;
                    nex[i] = nex[j];
                    nex[j] = i;
                    break;
                }
            }
            if(repr[i]==i) ac.insert(P[i],i+1);
        }
        ac.build();
        memset(cnt,0,sizeof(cnt));
        for(tr=0; tr<n; tr++){
            ac.Find(text[tr]);
        }
        int ans = 0;
        for(int i=0; i<n-x+1; i++){
            for(int j=0; j<m-y+1; j++){
                if(cnt[i][j]==x) ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}