1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010, M = 1010;
int n, m, k;
int son[N][26], cnt[N], idx;
int ne[N];
char g[M][M], str[M];
int q[N]; // 队列
int id[N]; // id[p]表示以p结尾(由于反过来存,因此实际表示的是开头)对应的查询编号
int dir[M]; // 存每个询问的方向
PII pos[M]; // 存每个询问的坐标
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int opposite[8] = {4, 5, 6, 7, 0, 1, 2, 3}; // 存每个方向的相反方向
void insert(int query_id, char str[]) {
int p = 0;
int len = strlen(str);
for (int i = len - 1; i >= 0; i--) {
int u = str[i] - 'A';
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
id[p] = query_id; // 以p结尾的单词对应的询问编号
}
void build() {
int hh = 0, tt = -1;
for (int i = 0; i < 26; i++) {
if (son[0][i]) q[++tt] = son[0][i];
}
while (hh <= tt) {
int t = q[hh++];
for (int i = 0; i < 26; i++) {
if (!son[t][i]) son[t][i] = son[ne[t]][i];
else {
ne[son[t][i]] = son[ne[t]][i];
q[++tt] = son[t][i];
}
}
}
}
// 判断是否越界
bool check(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void search(int sx, int sy, int t) { // 从(sx, sy)向t方向搜
for (int si = sx, sj = sy, j = 0; check(si, sj); si += dx[t], sj += dy[t]) {
int u = g[si][sj] - 'A';
j = son[j][u];
int k = j;
while (k) {
if (cnt[k]) {
int query_id = id[k];
pos[query_id] = make_pair(si, sj);
dir[query_id] = opposite[t];
}
cnt[k] = 0;
k = ne[k];
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; i++) scanf("%s", g[i]);
for (int i = 0; i < k; i++) {
scanf("%s", str);
insert(i, str);
}
build(); // 建立AC自动机
// 枚举四周边上的每一个字母,分别搜索8个方向
// 先枚举左右两侧的 即第0列和第m-1列的所有格子
for (int r = 0; r < n; r++) {
// 搜(r, 0)和(r, m - 1)
for (int j = 0; j < 8; j++) {
search(r, 0, j), search(r, m - 1, j);
}
}
// 再枚举上下两行 即第0行和第n-1行的所有格子
for (int c = 0; c < m; c++) {
for (int j = 0; j < 8; j++) {
search(0, c, j), search(n - 1, c, j);
}
}
// 给八个方向对应字母
map<int, char> mp;
for (int i = 0; i < 8; i++) mp[i] = 'A' + i;
// 输出每个询问对应的答案
for (int i = 0; i < k; i++) printf("%d %d %c\n", pos[i].x, pos[i].y, mp[dir[i]]);
return 0;
}
|