POJ 1204 AC自动机

题目就是给出了一个矩阵，由大写字母构成，然后让你查找某些单词在矩阵中出现的位置

出现的方式可能有8种，从某个位置往北连续的字符串，往东北，东........八个方向的只要有满足的 就可以

最后输出位置和方向，然后往北的输出时为A，东北的是B，依次顺时针类推

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 222200
#define INF 1000000000
using namespace std;
int e, cnt, L, C, W;
char s[MAXN][MAXN];
bool vis[MAXN];
int ansx[MAXN], ansy[MAXN], len[MAXN];
int loc[MAXN];
int tx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, ty[8] = {0, 1, 1, 1, 0, -1, -1, -1};
char dic[] = "ABCDEFGH";
char tmp[MAXN];
struct Trie
{
    int next[26];
    int fail, id;
    void init ()
    {
        memset(next, 0, sizeof(next));
        fail = -1;
        id = 0;
    }
} trie[MAXM];
void make_trie (char *str, int id)
{
    int i = 0, index, u = 0;
    while(str[i])
    {
        index = str[i] - 'A';
        if(!trie[u].next[index]) trie[u].next[index] = ++e;
        u = trie[u].next[index];
        i++;
    }
    trie[u].id = id;
}
int q[MAXM];
void make_ac_automation()
{
    int i, j;
    int h = 0,  t = 0;
    q[t++] = 0;
    while(h < t)
    {
        int u = q[h++];
        for(i = 0; i < 26; i++)
            if(trie[u].next[i])
            {
                int v = trie[u].next[i];
                for(j = trie[u].fail; j != -1; j = trie[j].fail)
                    if(trie[j].next[i])
                    {
                        trie[v].fail = trie[j].next[i];
                        break;
                    }
                if(j == -1) trie[v].fail = 0;
                q[t++] = v;
            }
    }
}
void match(int x, int y, int k)
{
    int u = 0, index;
    while(s[x][y])
    {
        index = s[x][y] - 'A';
        while(!trie[u].next[index] && u != 0) u = trie[u].fail;
        u = trie[u].next[index];
        if(u == -1) u = 0;
        int v = u;
        while(v != 0 && trie[v].id != -1)
        {
            if(trie[v].id > 0 && !vis[trie[v].id])
            {
                cnt++;
                vis[trie[v].id] = 1;
                ansx[trie[v].id] = x - (len[trie[v].id] - 1) * tx[k];
                ansy[trie[v].id] = y - (len[trie[v].id] - 1) * ty[k];
                loc[trie[v].id] = k;
                if(cnt == W) return;
            }
            trie[v].id = -1;
            v = trie[v].fail;
        }
        x += tx[k], y += ty[k];
    }
}
int main()
{
    for(int i = 0; i < MAXM; i++) trie[i].init();
    scanf("%d%d%d", &L, &C, &W);
    for(int i = 1; i <= L; i++) scanf("%s", s[i] + 1);
    for(int i = 1; i <= W; i++)
    {
        scanf("%s", tmp);
        make_trie(tmp, i);
        len[i] = strlen(tmp);
    }
    make_ac_automation();
    for(int i = 1; i <= C; i++)
        match(L, i, 0);//A
    for(int i = 1; i <= L; i++)
        match(i, 1, 1);//B
    for(int i = 1; i <= C; i++)
        match(L, i, 1);//B
    for(int i = 1; i <= L; i++)
        match(i, 1, 2);//C
    for(int i = 1; i <= C; i++)
        match(1, i, 3);//D
    for(int i = 1; i <= L; i++)
        match(i, 1, 3);
    for(int i = 1; i <= C; i++)
        match(1, i, 4);//E
    for(int i = 1; i <= L; i++)
        match(i, C, 5);//F
    for(int i = 1; i <= C; i++)
        match(1, i, 5);
    for(int i = 1; i <= L; i++)
        match(i, C, 6);//G
    for(int i = 1; i <= C; i++)
        match(L, i, 7);//H
    for(int i = 1; i <= L; i++)
        match(i, C, 7);
    for(int i = 1; i <= W; i++)
        if(vis[i]) printf("%d %d %c\n", ansx[i] - 1, ansy[i] - 1, dic[loc[i]]);
    return 0;
}