只要把每行的模版串插到ac自动机，然后匹配行，每次匹配成功，那一行对应的字符矩阵的左上角的计数器+1，最后统计下计数器矩阵有多少个左上角是行数的就可以了。
思路很简单，但想法很好，但要注意模版上有两行是一样的，插入到ac自动机的时候会插到同一个结点上，为了区分，我还是谨慎地开了个vector，然后1A了。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=12000; const int INF=1e9+10; int n,m; int x,y; char s[1200][1200],t[120][120]; int cnt[1200][1200]; struct Trie { int ch[maxn][26]; //int id[maxn];/// id[k] means kth row vector<int> id[maxn]; int f[maxn]; int last[maxn]; int rt,tot; int newnode() { ++tot; memset(ch[tot],-1,sizeof(ch[tot])); //id[tot]=0; id[tot].clear(); return tot; } void init() { REP(i,0,maxn-1) id[i].clear(); tot=-1; rt=newnode(); } void insert(char *s,int ID) { int len=strlen(s),u=rt; REP(i,0,len-1){ int c=s[i]-'a'; if(ch[u][c]==-1) ch[u][c]=newnode(); u=ch[u][c]; } id[u].push_back(ID); } void build() { queue<int> q; f[rt]=rt;last[rt]=rt; REP(c,0,25){ if(~ch[rt][c]) f[ch[rt][c]]=rt,q.push(ch[rt][c]); else ch[rt][c]=rt; } while(!q.empty()){ int u=q.front();q.pop(); REP(c,0,25){ if(~ch[u][c]) f[ch[u][c]]=ch[f[u]][c],q.push(ch[u][c]); else ch[u][c]=ch[f[u]][c]; if((int)id[f[u]].size()) last[u]=f[u]; else last[u]=last[f[u]]; } } } void get(int u,int row,int col) { if(!u) return; /// row-id[u]+1,col-y+1 for(int i=0;i<id[u].size();i++){ if(row-id[u][i]+1>0&&col-y+1>0) cnt[row-id[u][i]+1][col-y+1]++; } get(last[u],row,col); } void find(char *s,int ID) { int len=strlen(s),u=rt; REP(i,0,len-1){ int c=s[i]-'a'; u=ch[u][c]; if((int)id[u].size()) get(u,ID,i+1); else if(last[u]) get(last[u],ID,i+1); } } };Trie ac; int main() { freopen("in.txt","r",stdin); int T;cin>>T; while(T--){ ac.init(); scanf("%d%d",&n,&m); REP(i,1,n) scanf("%s",s[i]+1); scanf("%d%d",&x,&y); REP(i,1,x) scanf("%s",t[i]+1),ac.insert(t[i]+1,i); ac.build(); MS0(cnt); REP(i,1,n) ac.find(s[i]+1,i); int ans=0; REP(i,1,n-x+1) REP(j,1,m-y+1) if(cnt[i][j]==x) ans++; cout<<ans<<endl; } return 0; } /** 3 3 3 xxx xxx xxx 2 2 xx xx 1 1 x 1 1 y 3 3 abc bcd cde 2 2 bc cd */