UVA 11019 Matrix Matcher

해석: 하나의 행렬 을 정 하고 다른 행렬 이 이 행렬 에 나타 나 는 횟수 를 구하 십시오.
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 를 참고 할 수 있 습 니 다. 이 문제 의 1 차원 간략화 판 입 니 다.
 

#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;	//         

		vector<int>line;	//          ，          

		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<int>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
",ans);

	}

	return 0;

}