c/c++语言开发共享P3121 [USACO15FEB]审查(AC自动机)

题目：

p3121 [usaco15feb]审查（黄金）censoring (gold)

解析：

多字符串匹配，首先想到ac自动机
建立一个ac自动机
因为有删除和拼接这种操作，考虑用栈维护
顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走
我们再维护一个pos数组，用来维护trie树中节点对应在文本串中的位置

代码

#include <bits/stdc++.h> using namespace std; const int n = 1e5 + 10;  int n, num; int sta[n], pos[n];  char s[n], t[n];  struct node {     int fail, end;     int nx[26]; } e[n];  inline void trieinsert(char *s) {     int rt = 0, len = strlen(s);     for (int i = 0; i < len; ++i) {         int v = s[i] - 'a';         if (!e[rt].nx[v]) e[rt].nx[v] = ++num;         rt = e[rt].nx[v];     }     e[rt].end = len; }  queue<int>q; inline void getfail() {     for (int i = 0; i < 26; ++i) if (e[0].nx[i]) {             q.push(e[0].nx[i]);             e[e[0].nx[i]].fail = 0;         }     while (!q.empty()) {         int u = q.front();         q.pop();         for (int i = 0; i < 26; ++i) {             if (e[u].nx[i]) {                 e[e[u].nx[i]].fail = e[e[u].fail].nx[i];                 q.push(e[u].nx[i]);             } else e[u].nx[i] = e[e[u].fail].nx[i];         }     } }  void query(char *s) {     int rt = 0, top = 0, len = strlen(s);     for (int i = 0; i < len; ++i) {         rt = e[rt].nx[s[i] - 'a'];         sta[++top] = rt;         pos[top] = i;         if (e[rt].end) {             top -= e[rt].end;             rt = sta[top];         }     }     for (int i = 1; i <= top; ++i) printf("%c", s[pos[i]]);     putchar('n'); }  int main() {     cin >> t;     cin >> n;     for (int i = 1; i <= n; ++i) {         cin >> s;         trieinsert(s);     }     getfail();     query(t);     return 0; }