POJ 1204 AC自动机

本文主要是介绍POJ 1204 AC自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目就是给出了一个矩阵，由大写字母构成，然后让你查找某些单词在矩阵中出现的位置

出现的方式可能有8种，从某个位置往北连续的字符串，往东北，东........八个方向的只要有满足的 就可以

最后输出位置和方向，然后往北的输出时为A，东北的是B，依次顺时针类推

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 222200
#define INF 1000000000
using namespace std;
int e, cnt, L, C, W;
char s[MAXN][MAXN];
bool vis[MAXN];
int ansx[MAXN], ansy[MAXN], len[MAXN];
int loc[MAXN];
int tx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, ty[8] = {0, 1, 1, 1, 0, -1, -1, -1};
char dic[] = "ABCDEFGH";
char tmp[MAXN];
struct Trie
{int next[26];int fail, id;void init (){memset(next, 0, sizeof(next));fail = -1;id = 0;}
} trie[MAXM];
void make_trie (char *str, int id)
{int i = 0, index, u = 0;while(str[i]){index = str[i] - 'A';if(!trie[u].next[index]) trie[u].next[index] = ++e;u = trie[u].next[index];i++;}trie[u].id = id;
}
int q[MAXM];
void make_ac_automation()
{int i, j;int h = 0,  t = 0;q[t++] = 0;while(h < t){int u = q[h++];for(i = 0; i < 26; i++)if(trie[u].next[i]){int v = trie[u].next[i];for(j = trie[u].fail; j != -1; j = trie[j].fail)if(trie[j].next[i]){trie[v].fail = trie[j].next[i];break;}if(j == -1) trie[v].fail = 0;q[t++] = v;}}
}
void match(int x, int y, int k)
{int u = 0, index;while(s[x][y]){index = s[x][y] - 'A';while(!trie[u].next[index] && u != 0) u = trie[u].fail;u = trie[u].next[index];if(u == -1) u = 0;int v = u;while(v != 0 && trie[v].id != -1){if(trie[v].id > 0 && !vis[trie[v].id]){cnt++;vis[trie[v].id] = 1;ansx[trie[v].id] = x - (len[trie[v].id] - 1) * tx[k];ansy[trie[v].id] = y - (len[trie[v].id] - 1) * ty[k];loc[trie[v].id] = k;if(cnt == W) return;}trie[v].id = -1;v = trie[v].fail;}x += tx[k], y += ty[k];}
}
int main()
{for(int i = 0; i < MAXM; i++) trie[i].init();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", tmp);make_trie(tmp, i);len[i] = strlen(tmp);}make_ac_automation();for(int i = 1; i <= C; i++)match(L, i, 0);//Afor(int i = 1; i <= L; i++)match(i, 1, 1);//Bfor(int i = 1; i <= C; i++)match(L, i, 1);//Bfor(int i = 1; i <= L; i++)match(i, 1, 2);//Cfor(int i = 1; i <= C; i++)match(1, i, 3);//Dfor(int i = 1; i <= L; i++)match(i, 1, 3);for(int i = 1; i <= C; i++)match(1, i, 4);//Efor(int i = 1; i <= L; i++)match(i, C, 5);//Ffor(int i = 1; i <= C; i++)match(1, i, 5);for(int i = 1; i <= L; i++)match(i, C, 6);//Gfor(int i = 1; i <= C; i++)match(L, i, 7);//Hfor(int i = 1; i <= L; i++)match(i, C, 7);for(int i = 1; i <= W; i++)if(vis[i]) printf("%d %d %c\n", ansx[i] - 1, ansy[i] - 1, dic[loc[i]]);return 0;
}

这篇关于POJ 1204 AC自动机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---