View Code of Problem 1082

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int Max = 1005;
int r,c,w;
char puzzle[Max][Max];
char wd[Max*3];
int len[Max];
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};//up .... eight directions
char d[8] = {'E','F','G','H','A','B','C','D'};

struct Trie_Node
{
    Trie_Node* fail;
    Trie_Node* next[26];
    int value;
    Trie_Node()
    {
        value = 0;
        fail = NULL;
        memset(next,0,sizeof(next));
    }
};

void insertWord(Trie_Node* root, char* s, int len, int seq) //反向建立单词
{
    int del;
    Trie_Node* p = root;
    for(int i = len-1; i >= 0; i--)
    {
        del = s[i] - 'A';
        if(p->next[del] == NULL)
            p->next[del] = new Trie_Node();
        p = p->next[del];
    }
    p->value = seq;
}

void build_ac_automachine(Trie_Node* root)
{
    int i;
    queue<Trie_Node*> que;
    root->fail = NULL;
    for(i = 0; i < 26; i++)
    {
        if(root->next[i] != NULL)
        {
            root->next[i]->fail = root;
            que.push(root->next[i]);
        }
    }
    Trie_Node* now;
    while(!que.empty())
    {
        now = que.front();
        que.pop();
        for(i = 0; i < 26; i++)
        {
            if(now->next[i] == NULL)
                continue;
            Trie_Node* p = now->fail;
            while(p!=NULL&&p->next[i]==NULL)
                p = p->fail;
            if(p == NULL)
                now->next[i]->fail = root;
            else
                now->next[i]->fail = p->next[i];
            que.push(now->next[i]);
        }
    }
}

int X[Max],Y[Max],D[Max];

void SearchPatterns(Trie_Node* root, int i, int j, int k)
{
    int x=i,y=j;
    int del;
    Trie_Node* now = root;
    while(true)
    {
        if(x<0||x>=r||y<0||y>=c)
            break;
        del = puzzle[x][y]-'A';
        while(now->next[del]==NULL&&now!=root)
            now = now->fail;
        now = now->next[del];
        if(now == NULL)
            now = root;
        Trie_Node* p = now;
        while(p!=root&&p->value)
        {
            X[p->value] = x;
            Y[p->value] = y;
            D[p->value] = k;
            p->value = 0;
            p = p->fail;
        }
        x += dir[k][0];
        y += dir[k][1];
    }
}

int main()
{
    int i,j;
    Trie_Node* root = new Trie_Node();
    scanf("%d %d %d",&r,&c,&w);
    for(i = 0; i < r; i++)
        scanf("%s",puzzle[i]);
    for(i = 1; i <= w; i++)
    {
        scanf("%s",wd);
        len[i] = strlen(wd);
        insertWord(root,wd,strlen(wd),i);
    }
    build_ac_automachine(root);
    //8个方向上的查询
    for(i = 0; i < r; i++)
    {
        SearchPatterns(root,i,0,2);
        SearchPatterns(root,i,c-1,6);
        SearchPatterns(root,i,0,3);
        SearchPatterns(root,i,c-1,7);
        SearchPatterns(root,i,0,1);
        SearchPatterns(root,i,c-1,5);
    }
    for(j = 0; j < c; j++)
    {
        SearchPatterns(root,r-1,j,0);
        SearchPatterns(root,0,j,4);
        SearchPatterns(root,0,j,3);
        SearchPatterns(root,r-1,j,7);
        SearchPatterns(root,r-1,j,1);
        SearchPatterns(root,0,j,5);
    }
    for(i = 1; i <= w; i++)
        printf("%d %d %c\n",X[i],Y[i],d[D[i]]);
    return 0;
}