假设N*M矩阵为T，X*Y矩阵为P
方法是利用count[i][j]来记录以(i,j)为左上角，且大小为X，Y的矩形中含有多少个完整行与P矩阵对应行完全相同。
所以，如果在T矩阵的第r行的第c列开始与P的第i行匹配，那么count[r-i][c]++;
最后判断是否有count[][]==X;
PS:这题是AC自动机的进阶题目，可以参考HDU 2222,是这题的一维简化版
#include"stdio.h" #include"string.h" #include"stdlib.h" #include"queue" using namespace std; #define maxnode (100*100+10) #define sigma_size 26 int N,M,X,Y; char map[1005][1005]; int cnt[1005][1005]; struct AC_automation{ struct node{ int next[sigma_size]; int val; //树节点的附加信息 int fail; //存储节点的失配指针 vectorline; //记录该单词所在的行数，可能多个行的单词相等 void init(){ memset(next,0,sizeof(next)); line.clear(); fail = val = 0; } }ch[maxnode]; //用来存储Trie树 int sz; //整棵树节点的总数 int idx(char c){ return c - 'a'; //对于小写字母集,获得c的编号 } void init(){ sz = 1; ch[0].init(); } void insert(char *s,int v){ int u = 0,len = strlen(s); for(int i = 0 ; i < len ; i ++){ int c = idx(s[i]); if(ch[u].next[c] == 0){ ch[sz].init(); ch[u].next[c] = sz++; } u = ch[u].next[c]; } ch[u].val = 1; ch[u].line.push_back(v); } //利用bfs得到失配指针fail void get_fail(){ queue Q; for(int i = 0 ; i < sigma_size; i ++) if(ch[0].next[i] != 0) Q.push(ch[0].next[i]); while(!Q.empty()){ int temp = Q.front(); Q.pop(); for(int i = 0 ; i < sigma_size; i ++){ if(ch[temp].next[i] != 0){ Q.push(ch[temp].next[i]); int fail_temp = ch[temp].fail; //关键步骤，如果fail指针所指的节点没有('a'+i)这个子节点，继续递归，直到fail_temp指向0节点，即根节点 while(fail_temp > 0 && ch[fail_temp].next[i] == 0) fail_temp = ch[fail_temp].fail; if(ch[fail_temp].next[i] != 0) //如果fail_temp节点的子节点有('a'+i)这个字符 fail_temp = ch[fail_temp].next[i]; ch[ch[temp].next[i]].fail = fail_temp; //子节点的失配节点由父节点节点决定 } } } } //寻找text[]总共有多少个单词 void find(char *text,int x){ int len = strlen(text); int node = 0,fail_temp = 0; for(int i = 0 ; i < len ; i ++){ int character = idx(text[i]); while(fail_temp > 0 && ch[fail_temp].next[character] == 0) //若没有text[i]这个字符，则使用失配指针继续在Trie树上遍历 fail_temp = ch[fail_temp].fail; if(ch[fail_temp].next[character] != 0){ //此时找到了text[i]这个字符 fail_temp = ch[fail_temp].next[character]; int fail_temp2 = fail_temp; //此处必须有另一个变量来记录失配的时候的下标 while(fail_temp2 > 0 && ch[fail_temp2].val){ for(int j = 0 ; j < ch[fail_temp2].line.size(); j ++){ //枚举该单词所在的所有行 int temp = ch[fail_temp2].line[j]; if(x >= temp) cnt[x-temp][i] ++; } fail_temp2 = ch[fail_temp2].fail; } } } } }AC; int main(){ int T; scanf("%d",&T); while(T--){ AC.init(); memset(cnt,0,sizeof(cnt)); scanf("%d%d",&N,&M); for(int i = 0 ; i < N ; i ++) scanf("%s",map[i]); scanf("%d%d",&X,&Y); char str_temp[105]; for(int i = 0 ; i < X; i++){ scanf("%s",str_temp); AC.insert(str_temp,i); } AC.get_fail(); for(int i = 0 ; i < N ; i++){ AC.find(map[i],i); } int ans = 0; for(int i = 0 ; i < N; i ++){ for(int j = 0 ; j < M ; j ++){ if(cnt[i][j] == X) ans++; } } printf("%d\n",ans); } return 0; }