POJ_1204
其实POJ这个题目叙述得不太严谨，所以我就先做SPOJ上这个题去了，回来之后交了一下倒是也过了。
这个题目可以用AC自动机去做，为了能够在匹配完单词后顺利找到单词首位置，我们可以选择把单词反过来建字母树，这样最后一个字符实际上就是第一个字符。
在后面查找的时候可以做一个小优化，就是找过的字典树上的结点的标记置为-1，以后再遇到这个结点就直接break而没必要再沿着预处理的标记向上寻找了。
#include<stdio.h>
#include<string.h>
#define MAXD 800010
#define MAXN 1010
char b[MAXN][MAXN], word[MAXN];
int N, M, W, next[MAXD][26], flag[MAXD], P[MAXD], q[MAXD], e, dir[MAXN], tx[MAXN], ty[MAXN];
void insert(int cur, int k)
{
++ e;
flag[e] = 0;
memset(next[e], 0, sizeof(next[e]));
next[cur][k] = e;
}
void init()
{
int i, j, k, cur;
for(i = 0; i < N; i ++)
scanf("%s", b[i]);
e = 0;
memset(next[e], 0, sizeof(next[e]));
for(i = 1; i <= W; i ++)
{
scanf("%s", word);
cur = 0;
for(j = strlen(word) - 1; j >= 0; j --)
{
k = word[j] - 'A';
if(!next[cur][k])
insert(cur, k);
cur = next[cur][k];
}
flag[cur] = i;
}
}
void prepare()
{
int i, j, k, u, front, rear;
P[0] = front = rear = 0;
q[rear ++] = 0;
while(front < rear)
{
u = q[front ++];
for(i = 0; i < 26; i ++)
if(next[u][i])
{
k = next[u][i];
if(u == 0)
P[k] = 0;
else
{
for(j = P[u]; j > 0; j = P[j])
if(next[j][i])
{
P[k] = next[j][i];
break;
}
if(j == 0)
P[k] = next[0][i];
}
q[rear ++] = k;
}
}
}
void deal(int x, int y, int &j, int d)
{
int i, k, t;
k = b[x][y] - 'A';
while(j > 0 && !next[j][k])
j = P[j];
j = next[j][k];
for(t = j; t > 0; t = P[t])
{
if(flag[t] >= 0)
{
if(flag[t])
{
dir[flag[t]] = d;
tx[flag[t]] = x, ty[flag[t]] = y;
}
flag[t] = -1;
}
else
break;
}
}
void solve()
{
int i, j, k, t, x, y, dx, dy;
prepare();
for(x = 0; x < N; x ++)
{
j = 0;
for(y = 0; y < M; y ++)
deal(x, y, j, 6);
}
for(x = 0; x < N; x ++)
{
j = 0;
for(y = M - 1; y >= 0; y --)
deal(x, y, j, 2);
}
for(y = 0; y < M; y ++)
{
j = 0;
for(x = 0; x < N; x ++)
deal(x, y, j, 0);
}
for(y = 0; y < M; y ++)
{
j = 0;
for(x = N - 1; x >= 0; x --)
deal(x, y, j, 4);
}
dx = 1, dy = 1;
for(i = M - 1; i >= 0; i --)
{
j = 0;
for(x = 0, y = i; x < N && y < M; x += dx, y += dy)
deal(x, y, j, 7);
}
for(i = 1; i < N; i ++)
{
j = 0;
for(x = i, y = 0; x < N && y < M; x += dx, y += dy)
deal(x, y, j, 7);
}
dx = -1, dy = -1;
for(i = 0; i < M; i ++)
{
j = 0;
for(x = N - 1, y = i; x >= 0 && y >= 0; x += dx, y += dy)
deal(x, y, j, 3);
}
for(i = N - 2; i >= 0; i --)
{
j = 0;
for(x = i, y = M - 1; x >= 0 && y >= 0; x += dx, y += dy)
deal(x, y, j, 3);
}
dx = 1, dy = -1;
for(i = 0; i < M; i ++)
{
j = 0;
for(x = 0, y = i; x < N && y >= 0; x += dx, y += dy)
deal(x, y, j, 1);
}
for(i = 1; i < N; i ++)
{
j = 0;
for(x = i, y = M - 1; x < N && y >= 0; x += dx, y += dy)
deal(x, y, j, 1);
}
dx = -1, dy = 1;
for(i = 0; i < N; i ++)
{
j = 0;
for(x = i, y = 0; x >= 0 && y < M; x += dx, y += dy)
deal(x, y, j, 5);
}
for(i = 1; i < M - 1; i ++)
{
j = 0;
for(x = N - 1, y = i; x >= 0 && y < M; x += dx, y += dy)
deal(x, y, j, 5);
}
for(i = 1; i <= W; i ++)
printf("%d %d %c\n", tx[i], ty[i], dir[i] + 'A');
}
int main()
{
while(scanf("%d%d%d", &N, &M, &W) == 3)
{
init();
solve();
}
return 0;
}