ahocorasick.cpp (2)

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

const int N = 1003;

int m, n;

char a[N][N];  //

int k, dx[N], dy[N], doo[N];

bool Explored[N];      //

int Same[N], Less[N];  //

namespace trie {

int a[N * N][32], Peak = 0;  //

#define a(u, k) a[u][k & 31]

int Success[N * N], Prev[N * N];  //

void insert(char s[], int Key) {

    int u = 0;

    for (int i = 0; char k = s[i]; i++)

        u = a(u, k) ? a(u, k) : a(u, k) = ++Peak;

    Same[Key] = Success[u];

    Success[u] = Key;

}  // done Same, a

int next(int u, char k) {

    for (int i = u; i != -1; i = Prev[i])

        if (a(i, k)) return a(i, k);

    return 0;

}

void bfs() {

    queue<int> qu;

    qu.push(0);

    Prev[0] = -1;

    Success[0] = 0;

    while (qu.size()) {

        int u = qu.front();

        qu.pop();

        for (int k = 0; k < 32; k++)

            if (int v = a(u, k)) {

                Prev[v] = next(Prev[u], k);

                if (Success[v])

                    Less[Success[v]] = Success[u];

                else

                    Success[v] = Success[u];

                qu.push(v);

            }

    }

}  // done Prev, Success,

};  // namespace trie

void explore(int u, int x, int y, int o) {

    for (int i = u; !Explored[i]; i = Less[i])

        for (int j = i; !Explored[j]; j = Same[j]) {

            Explored[j] = true;

            dx[j] = x;

            dy[j] = y;

            doo[j] = o;

            //printf("explored %d = %d, %d, %d\n", j, x, y, o);

        }

}

void solve(int x, int y, int rx, int ry, int o) {

    int u = 0;

    for (int i = x, j = y; a[i][j]; i += rx, j += ry) {

        u = trie ::next(u, a[i][j]);

        if (!Explored[trie ::Success[u]])

            explore(trie ::Success[u], i, j, o);

    }

}

void solve() {

    scanf("%d%d%d", &m, &n, &k);

    for (int i = 1; i <= m; i++)

        scanf("%s", a[i] + 1);

    for (int i = 1; i <= k; i++) {

        char s[N];

        scanf("%s", s);

        reverse(s, s + strlen(s));

        trie ::insert(s, i);

    }

    trie ::bfs();

    for (int i = 1; i <= m; i++) {

        solve(i, 1, -1, +1, 3);

        solve(i, 1, 0, +1, 6);

        solve(i, 1, +1, +1, 9);

        solve(i, n, -1, -1, 1);

        solve(i, n, 0, -1, 4);

        solve(i, n, +1, -1, 7);

    }

    for (int i = 1; i <= n; i++) {

        solve(1, i, +1, -1, 7);

        solve(1, i, +1, 0, 8);

        solve(1, i, +1, +1, 9);

        solve(m, i, -1, -1, 1);

        solve(m, i, -1, 0, 2);

        solve(m, i, -1, +1, 3);

    }

    char Dir[] = "?DEFC?GBAH";

    for (int i = 1; i <= k; i++)

        printf("%d %d %c\n", dx[i] - 1, dy[i] - 1, Dir[doo[i]]);

}

int main() {

    int t;

    scanf("%d", &t);

    while (t--) {

        solve();

        if (t) puts("");

#define memset(a) memset(a, 0, sizeof a)

#define apply4(f, a, b, c, d) f(a), f(b), f(c), f(d)

#define apply3(f, a, b, c) f(a), f(b), f(c)

        trie ::Peak = 0;

        apply4(memset, a, Explored, Same, Less);

        apply3(memset, trie::a, trie::Success, trie::Prev);

    }

}