UVA 11019 Matrix Matcher

<pre name="code" class="cpp">#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\n",ans);  
    }  
    return 0;  
}</pre><br><br>