Uva(11019)(Matrix Matcher)

链接：https://vjudge.net/problem/UVA-11019
思路：我们需要改造一下就可以变成一个自动机的题目，我们把需要查找的矩阵按行拆成母串，然后构成一个trie图，用val记录他在原矩阵中的行数，然后将大的那个矩阵拆分成行依次进行匹配，当匹配成功就将对应的矩阵左上角顶点的值++，当某一个点的值等于小矩阵的行数的时候，就说明找到了一个矩阵。
注意事项：做自动机时一定要考虑到母串可能重叠覆盖的问题，对于本题可以将val改造成一个vector，记录每个的对应行数，还有一个就是注意内存问题，自动机的题很容易超内存！
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxnode = 1e6+10;
const int sigma_size = 26;
int t,n,m,x,y;
char str1[1010][1010];
char str2[1010][1010];

struct AC{
    int ch[maxnode][sigma_size];
    int num[1010][1010];
    int sz;
    vector<int> val[maxnode];
    int f[maxnode];

    void init(){
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
        memset(num,0,sizeof(num));
        val[0].clear();
    }

    inline int idx(char c){
        return c-'a';
    }

    void insert(char *s,int r){
        int u=0;
        int n = strlen(s);
        for(int i=0;i<n;i++){
            int c = idx(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(r);
    }

    void getfail(){
        queue<int> q;
        f[0] = 0;
        for(int c=0;c<sigma_size;c++){
            int u = ch[0][c];
            if(u){
                f[u] = 0;
                q.push(u);
            }
        }
        while(!q.empty()){
            int r = q.front();
            q.pop();
            for(int c=0;c<sigma_size;c++){
                int u = ch[r][c];
                if(!u){
                    ch[r][c] = ch[f[r]][c];
                    continue;
                }
                q.push(u);
                int v = f[r];
                while(v&&!ch[v][c])v = f[v];
                f[u] = ch[v][c];
            }
        }
    }

    void print(int i,int j,int k){
      //  printf("%d %d\n",i,j);
        if(i-k+1>0&&j-y+1>0)
        num[i-k+1][j-y+1]++;//对应的矩阵的左上角的顶点值++
    }

    void find(char *s,int r){
        int n = strlen(s);
        int j = 0;
        for(int i=0;i<n;i++){
            int c = idx(s[i]);
            j = ch[j][c];
            if(val[j].size()){
                for(int p=0;p<val[j].size();p++)
                print(r,i+1,val[j][p]);
            }
        }
    }
}solver;

int main(){
    scanf("%d",&t);
    while(t--){
        solver.init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%s",str1[i]);
        }
        scanf("%d%d",&x,&y);
        for(int i=1;i<=x;i++){
            scanf("%s",str2[i]);
            solver.insert(str2[i],i);
        }
        solver.getfail();
        for(int i=1;i<=n;i++){
            solver.find(str1[i],i);
        }
        int  ans = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(solver.num[i][j]==x)ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}