本文共 3602 字，大约阅读时间需要 12 分钟。

AC自动机 - Word Puzzles - POJ - 1204

题意：

$$\begin{gathered} 给定一个l\times c的字符矩阵，以及w个字符串，需要找出w个字符串在矩阵中出现的位置。 \\ 输出字符串第一个字符的坐标以及字符串的“方向”(共8个方向)， \\ 由8个字母A-H表示8个方向，从A开始代表北，顺时针依次为B,C,D,...,H。 \end{gathered}$$

Sample Input：20 20 10QWSPILAATIRAGRAMYKEIAGTRCLQAXLPOIJLFVBUQTQTKAZXVMRWALEMAPKCWLIEACNKAZXKPOTPIZCEOFGKLSTCBTROPICALBLBCJEWHJEEWSMLPOEKORORALUPQWRNJOAAGJKMUSJAEKRQEIOLOAOQPRTVILCBZQOPUCAJSPPOUTMTSLPSFLPOUYTRFGMMLKIUISXSWWAHCPOIYTGAKLMNAHBVAEIAKHPLBGSMCLOGNGJMLLDTIKENVCSWQAZUAOEALHOPLPGEJKMNUTIIORMNCLOIUFTGSQACAXMOPBEIOQOASDHOPEPNBUYUYOBXBIONIAELOJHSWASMOUTRKHPOIYTJPLNAQWDRIBITGLPOINUYMRTEMPTMLMNBOPAFCOPLHAVAIANALBPFSMARGARITAALEMABARBECUETROPICALSUPREMALOUISIANACHEESEHAMEUROPAHAVAIANACAMPONESASample Output：0 15 G2 11 C7 18 A4 8 C16 13 B4 15 E10 3 D5 1 E19 7 C11 11 H

数据范围：

题解：

$对k个字符串建Trie图，接着对每个字符暴力搜索八个方向在图上匹配，记下匹配成功的坐标和方向即可。$

具体落实：

$$\begin{gathered} ①、建Trie图，插入的过程中给每个结尾字符打标记，每个单词的id记为其输入的序号，方便匹配成功的判断。 \\ ②、爆搜的过程可以从矩阵四条边上的点进入，来减少重复搜索，同时也能避免遗漏，保证每种可能性均被搜到。 \end{gathered}$$

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        const int N=1010;using namespace std;int l, c, idx = 1, w,ans[N][3], len[N];char s[N][N], s2[N],dir[N];int dx[] = {    -1, -1, 0, 1, 1, 1, 0, -1 };int dy[] = {    0, 1, 1, 1, 0, -1, -1, -1 };struct node{       int tr[30], id, fail;}e[N * 110];void Insert(char *str,int x){       int u = 1;    for (int i = 0;str[i]; i++)    {           int t = str[i] - 'A';        if (!e[u].tr[t])            e[u].tr[t] = ++idx;        u = e[u].tr[t];    }    e[u].id = x;}void build(){       for (int i = 0; i < 26; i++)        e[0].tr[i] = 1;    queue 
        
          q; q.push(1); while (!q.empty()) { int u = q.front(); q.pop(); int fail = e[u].fail; for (int i = 0; i < 26; i++) { int y = e[u].tr[i]; if (y) { e[y].fail = e[fail].tr[i]; q.push(y); } else e[u].tr[i] = e[fail].tr[i]; } }}void dfs(int sx, int sy, int d){ int x = sx, y = sy, u = 1; while (x >= 1 && x <= l && y >= 1 && y <= c) { while (u && !e[u].tr[s[x][y] - 'A']) u = e[u].fail; u = e[u].tr[s[x][y] - 'A']; if (e[u].id) { ans[e[u].id][1] = x - (len[e[u].id] - 1) * dx[d]; ///回到第一个字母 ans[e[u].id][2] = y - (len[e[u].id] - 1) * dy[d]; dir[e[u].id] = d; } x += dx[d]; y += dy[d]; }}int main(){ scanf("%d%d%d", &l, &c, &w); for (int i = 1; i <= l; i++) scanf("%s", s[i] + 1); for (int i = 1; i <= w; i++) { scanf("%s", s2); len[i] = strlen(s2); Insert(s2,i); } build(); for (int i = 1; i <= l; i++) for (int j = 0; j < 8; j++) dfs(i, 1, j), dfs(i, c, j); for (int i = 1; i <= c; i++) for (int j = 0; j < 8; j++) dfs(1, i, j), dfs(l, i, j); for (int i = 1; i <= w; i++) printf("%d %d %c\n", ans[i][1] - 1, ans[i][2] - 1, dir[i] + 'A'); return 0;}