题目:
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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602523.html