Problem H
Matrix Matcher
Input: Standard Input

Output: Standard Output

Given an N * M matrix, your task is to find the number of occurences of an X * Y pattern.

Input

The first line contains a single integer t(t ≤ 15), the number of test cases.

For each case, the first line contains two integers N and M (N, M ≤ 1000). The next N lines contain M characters each.

The next line contains two integers X and Y (X, Y ≤ 100). The next X lines contain Y characters each.

Output

For each case, output a single integer in its own line, the number of occurrences.

Sample Input Output for Sample Input

2

1 1

x

1 1

y

3 3

abc

bcd

cde

2 2

bc

cd

Problem Setter: Rujia Liu, EPS

Special Thanks: Wenbin Tang

Warming: The judge input file size is about 7 MB. So please make sure that you use a fast IO function (eg.scanf()) to read input.

每次成功匹配，就把以当前行匹配算出来的矩阵的右上角cnt++，被+x次说明匹配矩阵成功。

注意vector中的元素用(*it)

PS：由于P中单词长度一致，故不用在print循环last

PS2:有可能同一行出现2次覆盖v，因此要用vector

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i
             
              =0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define MAXT (15+10) #define MAXN (1000+10) #define MAXX (100+10) #define MAXNode (1000000) #define Sigma_size (26) typedef long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int cnt[MAXN][MAXN]; //右上角 class Aho_Corasick_Automata { public: int ch[MAXNode][Sigma_size],siz; vector
              
                v[MAXNode]; // AC自动机 int f[MAXNode],last[MAXNode]; Aho_Corasick_Automata(int _siz=0):siz(_siz){MEM(ch) Rep(i,MAXNode) v[i].clear(); MEM(f) MEM(last)} void mem(int _siz=0){siz=_siz; MEM(ch) Rep(i,MAXNode) v[i].clear(); MEM(f) MEM(last) } int idx(char c){return c-'a';} void insert(char *s,int val=1) //val!=0 表示单词末尾， PS:lrj叫它单词节点 { int u=0,n=strlen(s); Rep(i,n) { int c=idx(s[i]); if (!ch[u][c]) { ++siz; MEM(ch[siz]); ch[u][c]=siz; } u=ch[u][c]; } v[u].push_back(val); } void getFail() { queue
               
                 q; Rep(c,Sigma_size) { int u=ch[0][c]; if (u) q.push(u),last[u]=0; } while (!q.empty()) { int r=q.front();q.pop(); //r--c-->u Rep(c,Sigma_size) { int u=ch[r][c]; if (!u) {ch[r][c]=ch[f[r]][c]; continue;} q.push(u); f[u]=ch[f[r]][c]; last[u]=v[f[u]].size()?f[u]:last[f[u]]; } } } void print(int j,int r,int c) //打印全串中所有以j为末尾的str { for(vector
                
                 ::iterator it=v[j].begin();it!=v[j].end();it++) { int P_i=(*it); if (r-(P_i-1)<0) continue ; cnt[r-(P_i-1)][c]++; } } void find(char *s,int r) { int u=0,n=strlen(s); Rep(i,n) { int c=idx(s[i]); u=ch[u][c]; if (v[u].size()) print(u,r,i); else if (last[u]) print(u,r,i); } } }T; int n,m,x,y; char s[MAXN][MAXN]; char s2[MAXN]; int main() { // freopen("uva11019.in","r",stdin); // freopen(".out","w",stdout); int tt; scanf("%d",&tt); while(tt--) { T.mem(); scanf("%d%d",&n,&m); Rep(i,n) { scanf("%s",s[i]); } scanf("%d%d",&x,&y); For(i,x) { scanf("%s",s2); T.insert(s2,i); } T.getFail(); MEM(cnt) Rep(i,n) { char *str=s[i]; T.find(str,i); } int ans=0; Rep(i,n) { Rep(j,m) ans+=(bool)(cnt[i][j]==x); } cout<