[JSOI 2012] 玄武密码

#include<bits/stdc++.h>using namespace std;const int MAXN = 1e7 + 10;const int MAXM = 1e5 + 10;const int MAXLEN = 110;int n,m;int ans[MAXM];char P[MAXN];char s[MAXM][MAXLEN];inline int get_value(char a){ ???????if (a == ‘E‘) return 0; ???????if (a == ‘S‘) return 1; ???????if (a == ‘W‘) return 2; ???????if (a == ‘N‘) return 3;} struct AC_Automation{ ???????int tot; ???????int root; ???????struct Node ???????{ ???????????????int child[4]; ???????????????int fail; ???????????????bool visited; ???????} trie[MAXN]; ???????inline void insert(char *s) ???????{ ???????????????int now = root; ???????????????int len = strlen(s + 1); ???????????????????for (int i = 1; i <= len; i++) ???????????????{ ???????????????????????int val = get_value(s[i]); ???????????????????????if (!trie[now].child[val]) trie[now].child[val] = ++tot; ???????????????????????now = trie[now].child[val]; ???????????????????} ???????????} ???????????????inline void rebuild() ???????{ ???????????????int l,r; ???????????????static int q[MAXN]; ???????????????q[l = r = 1] = root; ???????????????trie[root].fail = -1; ???????????????while (l <= r) ???????????????{ ???????????????????????int cur = q[l]; ???????????????????????l++; ???????????????????????for (int i = 0; i < 4; i++) ???????????????????????{ ???????????????????????????????if (trie[cur].child[i]) ???????????????????????????????{ ???????????????????????????????????????if (cur == root) ???????????????????????????????????????????????trie[trie[cur].child[i]].fail = 0; ???????????????????????????????????????else ???????????????????????????????????????{ ???????????????????????????????????????????????int p = trie[cur].fail; ???????????????????????????????????????????????while (p != -1) ???????????????????????????????????????????????{ ???????????????????????????????????????????????????????if (trie[p].child[i]) ????????????????????????????????????????????????????????{ ???????????????????????????????????????????????????????????????trie[trie[cur].child[i]].fail = trie[p].child[i]; ???????????????????????????????????????????????????????????????break; ???????????????????????????????????????????????????????} else p = trie[p].fail; ???????????????????????????????????????????????} ???????????????????????????????????????} ???????????????????????????????????????q[++r] = trie[cur].child[i]; ????????????????????????????????} ???????????????????????} ???????????????} ???????} ???????inline void getans(char *s) ???????{ ???????????????int now = root; ???????????????int len = strlen(s + 1); ???????????????for (int i = 1; i <= len; i++) ???????????????{ ???????????????????????int val = get_value(s[i]); ???????????????????????int p = now; ???????????????????????while (p != -1) ???????????????????????{ ???????????????????????????????if (trie[p].child[val]) break; ???????????????????????????????else p = trie[p].fail; ???????????????????????} ???????????????????????if (p == -1) ????????????????????????{ ???????????????????????????????now = 0; ???????????????????????????????continue; ???????????????????????} else now = p = trie[p].child[val]; ???????????????????????while (p) ???????????????????????{ ???????????????????????????????if (!trie[p].visited) ???????????????????????????????{ ???????????????????????????????????????trie[p].visited = true; ???????????????????????????????????????p = trie[p].fail; ???????????????????????????????} else break; ???????????????????????} ???????????????} ???????} ???????inline void calc(int pos,char *s) ???????{ ???????????????int now = root; ???????????????int len = strlen(s + 1); ???????????????for (int i = 1; i <= len; i++) ???????????????{ ???????????????????????int val = get_value(s[i]); ???????????????????????now = trie[now].child[val]; ???????????????????????if (trie[now].visited) ans[pos] = i; ???????????????} ???????}} ACAM;int main() { ???????????????scanf("%d%d",&n,&m); ???????scanf("%s",P + 1); ???????for (int i = 1; i <= m; i++) scanf("%s",s[i] + 1); ???????for (int i = 1; i <= m; i++) ACAM.insert(s[i]); ???????ACAM.rebuild(); ???????ACAM.getans(P); ???????for (int i = 1; i <= m; i++) ACAM.calc(i,s[i]); ???????for (int i = 1; i <= m; i++) printf("%d\n",ans[i]); ???????????????return 0; ???}