#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; int const MAX = 1005; char map[MAX][MAX], s[MAX]; int r, c, n; int len[MAX], ans[MAX][3]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; struct node { int id; node *next[26]; node *fail; node() { id = -1; memset(next, NULL, sizeof(next)); fail = NULL; } }; void Insert(node *p, char *s, int id) { for(int i = 0; s[i] != '\0'; i++) { int idx = s[i] - 'A'; if(p -> next[idx] == NULL) p -> next[idx] = new node(); p = p -> next[idx]; } p -> id = id; } void AC_Automation(node *root) { queue <node*> q; q.push(root); while(!q.empty()) { node *p = q.front(); q.pop(); for(int i = 0; i < 26; i++) { if(p -> next[i]) { if(p == root) p -> next[i] -> fail = root; else p -> next[i] -> fail = p -> fail -> next[i]; q.push(p -> next[i]); } else { if(p == root) p -> next[i] = root; else p -> next[i] = p -> fail -> next[i]; } } } } bool judge(int i, int j) { if(i >= 0 && i < r && j >= 0 && j < c) return true; return false; } void Query(node *root, int x, int y, int k) { node *p = root; for(int i = x, j = y; judge(i, j); i += dx[k], j += dy[k]) { int idx = map[i][j] - 'A'; while(!p -> next[idx] && p != root) p = p -> fail; p = p -> next[idx]; if(!p) { p = root; continue; } node *tmp = p; while(tmp != root) { //找到单词,则记录下来相关信息 if(tmp -> id != -1) { int id = tmp -> id; ans[id][0] = i - len[id] * dx[k]; ans[id][1] = j - len[id] * dy[k]; ans[id][2] = k; tmp -> id = -1; } else break; tmp = tmp -> fail; } } } int main() { scanf("%d %d %d", &r, &c, &n); node *root = new node(); for(int i = 0; i < r; i++) scanf("%s", map[i]); for(int i = 0; i < n; i++) { scanf("%s", s); len[i] = strlen(s) - 1; Insert(root, s, i); } AC_Automation(root); //枚举各个边界的各个方向 for(int i = 0; i < c; i++) { for(int dir = 0; dir < 8; dir++) { Query(root, 0, i, dir); Query(root, r - 1, i, dir); } } for(int i = 0; i < r; i++) { for(int dir = 0; dir < 8; dir++) { Query(root, i, 0, dir); Query(root, i, c - 1, dir); } } for(int i = 0; i < n; i++) printf("%d %d %c\n", ans[i][0], ans[i][1], ans[i][2] + 'A'); } |
Double click to view unformatted code.