翻译洛谷有，但输入格式好像不太一样，注意一下。
这题我看了5分钟才把题看懂，知道是有关AC自动机的，然而就是想不出来。
我一直觉得应该把这张图建一个trie树，毕竟图作为主串，然后看模式串是否出现在主串里。
然而实际上是模式串建trie树。
然后题中说要判断8个方向是否有模式串出现，那么就把图中8个方向形成的字符串都放到AC自动机上跑一下。我刚开始以为会超时，但复杂度最多为O(8 * n2)，只有8e6，而AC自动机是线性的，所以TLE不了。
关于遍历八个方向上的字符串，写起来得动动脑子，可以联想到bfs或dfs跑图的时候用到的方向数组。
然后有因为AC自动机找到的匹配点是模式串的末尾，所以我们还要在这个方向上减去模式串的长度。
然后就是AC自动机的板子了。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e3 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), las = ' '; 25 while(!isdigit(ch)) las = ch, ch = getchar(); 26 while(isdigit(ch)) ans = ans * 10 + ch - '0', ch = getchar(); 27 if(las == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) putchar('-'), x = -x; 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m, w; 38 char a[maxn][maxn], s[maxn]; 39 40 int len[maxn]; 41 int ch[maxn * maxn][26], val[maxn * maxn], f[maxn * maxn], cnt = 0; 42 int getnum(char c) 43 { 44 return c - 'A'; 45 } 46 void insert(int id, char *s) 47 { 48 len[id] = strlen(s); 49 int now = 0; 50 for(int i = 0; i < len[id]; ++i) 51 { 52 int c = getnum(s[i]); 53 if(!ch[now][c]) ch[now][c] = ++cnt; 54 now = ch[now][c]; 55 } 56 val[now] = id; 57 } 58 void build() 59 { 60 queue<int> q; 61 for(int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]); 62 while(!q.empty()) 63 { 64 int now = q.front(); q.pop(); 65 for(int i = 0; i < 26; ++i) 66 { 67 if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]); 68 else ch[now][i] = ch[f[now]][i]; 69 } 70 } 71 } 72 const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; 73 struct Node 74 { 75 int x, y, d; 76 }ans[maxn]; 77 void query(int x, int y, int d) 78 { 79 int newx = x, newy = y, now = 0; 80 do 81 { 82 int c = getnum(a[newx][newy]); 83 now = ch[now][c]; 84 for(int j = now; j && val[j] != -1; j = f[j]) if(val[j] > 0) 85 { 86 ans[val[j]].x = newx - (len[val[j]] - 1) * dx[d]; 87 ans[val[j]].y = newy - (len[val[j]] - 1) * dy[d]; 88 ans[val[j]].d = d; 89 val[j] = -1; 90 } 91 newx += dx[d]; newy += dy[d]; 92 }while(newx >= 0 && newx < n && newy >= 0 && newy < m); 93 } 94 95 int main() 96 { 97 n = read(); m = read(); w = read(); 98 for(int i = 0; i < n; ++i) scanf("%s", a[i]); 99 for(int i = 1; i <= w; ++i) 100 { 101 scanf("%s", s); 102 insert(i, s); 103 } 104 build(); 105 for(int i = 0; i < n; ++i) 106 { 107 query(i, 0, 2); query(i, m - 1, 6); 108 query(i, 0, 1); query(i, m - 1, 5); 109 query(i, 0, 3); query(i, m - 1, 7); 110 } 111 for(int i = 0; i < m; ++i) 112 { 113 query(n - 1, i, 0); query(0, i, 4); 114 query(n - 1, i, 1); query(0, i, 5); 115 query(0, i, 3); query(n - 1, i, 7); 116 } 117 for(int i = 1; i <= w; ++i) printf("%d %d %c ", ans[i].x, ans[i].y, ans[i].d + 'A'); 118 return 0; 119 }
USACO上是多组数据，所以一定得清零，而且必须是动态的。然后我因为根节点的所有出边没清零而莫名TLE好久。
放一个比较好看的代码。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e3 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), las = ' '; 25 while(!isdigit(ch)) las = ch, ch = getchar(); 26 while(isdigit(ch)) ans = ans * 10 + ch - '0', ch = getchar(); 27 if(las == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) putchar('-'), x = -x; 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m, w; 38 char a[maxn][maxn], s[maxn]; 39 40 int len[maxn]; 41 int ch[maxn * maxn][26], val[maxn * maxn], f[maxn * maxn], cnt = 0; 42 inline int getnum(const char& c) 43 { 44 return c - 'A'; 45 } 46 inline void insert(const int& id, char *s) 47 { 48 int now = 0; 49 for(; *s; s++) 50 { 51 int c = getnum(*s); 52 if(!ch[now][c]) 53 { 54 ch[now][c] = ++cnt; 55 val[cnt] = f[cnt] = 0; 56 for(rg int j = 0; j < 26; ++j) ch[cnt][j] = 0; 57 } 58 now = ch[now][c]; 59 } 60 val[now] = id; 61 return; 62 } 63 queue<int> q; 64 inline void build() 65 { 66 for(rg int i = 0; i < 26; ++i) if(ch[0][i]) q.push(ch[0][i]); 67 while(!q.empty()) 68 { 69 int now = q.front(); q.pop(); 70 for(rg int i = 0; i < 26; ++i) 71 { 72 if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]); 73 else ch[now][i] = ch[f[now]][i]; 74 } 75 } 76 return; 77 } 78 const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; 79 struct Node 80 { 81 int x, y, d; 82 }ans[maxn]; 83 void query(const int& x, const int& y, const int& d) 84 { 85 int newx = x, newy = y, now = 0; 86 do 87 { 88 int c = getnum(a[newx][newy]); 89 now = ch[now][c]; 90 for(rg int j = now; j && val[j] != -1; j = f[j]) if(val[j] > 0) 91 { 92 ans[val[j]].x = newx - (len[val[j]] - 1) * dx[d]; 93 ans[val[j]].y = newy - (len[val[j]] - 1) * dy[d]; 94 ans[val[j]].d = d; 95 val[j] = -1; 96 } 97 newx += dx[d]; newy += dy[d]; 98 }while(newx >= 0 && newx < n && newy >= 0 && newy < m); 99 } 100 101 int main() 102 { 103 int T = read(); 104 while(T--) 105 { 106 cnt = 0; 107 for(int i = 0; i < 26; ++i) ch[0][i] = 0; 108 n = read(); m = read(); w = read(); 109 for(rg int i = 0; i < n; ++i) scanf("%s", a[i]); 110 for(rg int i = 1; i <= w; ++i) 111 { 112 scanf("%s", s); 113 len[i] = strlen(s); 114 insert(i, s); 115 } 116 build(); 117 for(rg int i = 0; i < n; ++i) 118 { 119 query(i, 0, 2); query(i, m - 1, 6); //hengzhe 120 query(i, 0, 1); query(i, m - 1, 5); 121 query(i, 0, 3); query(i, m - 1, 7); 122 } 123 for(rg int i = 0; i < m; ++i) 124 { 125 query(n - 1, i, 0); query(0, i, 4); 126 query(n - 1, i, 1); query(0, i, 5); 127 query(0, i, 3); query(n - 1, i, 7); 128 } 129 for(rg int i = 1; i <= w; ++i) printf("%d %d %c ", ans[i].x, ans[i].y, ans[i].d + 'A'); 130 if(T) enter; 131 } 132 return 0; 133 }