P3121 [USACO15FEB]审查(AC自动机)

2019-08-16 07:55:31来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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;
}

原文链接:https://www.cnblogs.com/lykkk/p/11265566.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:高精度算法之大整数类

下一篇:Nikitosh 和异或(trie树)