HDU 5880 – Family View [AC自动机]

Link

http://acm.hdu.edu.cn/showproblem.php?pid=5880

Problem

Steam is a digital distribution platform developed by Valve Corporation offering digital rights management (DRM), multiplayer gaming and social networking services. A family view can help you to prevent your children access to some content which are not suitable for them.

Take an MMORPG game as an example, given a sentence T, and a list of forbidden words {P}, your job is to use ‘*’ to subsititute all the characters, which is a part of the substring matched with at least one forbidden word in the list (case-insensitive).

For example, T is: “I love Beijing’s Tiananmen, the sun rises over Tiananmen. Our great leader Chairman Mao, he leades us marching on.”

And {P} is: {“tiananmen”, “eat”}

The result should be: “I love Beijing’s *********, the sun rises over *********. Our gr*** leader Chairman Mao, he leades us marching on.”

Mean

给N个小写字母构成的单词，和一个文本串。要求把文本串中出现的所有单词置为星号并输出。串最长为1000000.

Analysis

这题是2016青岛区域赛网络赛的题目，最后一小时才看这道题，已经没有时间了，其实就是AC自动机水题，今天套个模板就1A了…好可惜….

首先将模板串加入到AC自动机，并且build一下。因为文本串中含有各种字符，我们可以将字母变为小写，其他字符变为‘z’+1。这样就能在自动机里统一处理，sigma_size = 27即可。

最后记录一下以每个字母为起点到右边最长禁止长度，最后输出一下就好了。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000100;
char s[maxn], t[maxn];
int N, len[maxn], Len;
int ban[maxn];

struct ACAutomate {
    static const int maxnode = maxn, sigma_size = 27;
    int ch[maxnode][sigma_size], val[maxnode], sz;
    int f[maxnode], last[maxnode];

    void clear() {
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
        val[0] = 0;
    }
    int idx(char x) {
        return x - 'a';
    }

    void insert(const char *s, int v) {
        int u = 0;
        for(int i = 0; s[i]; ++i) {
            int id = idx(s[i]);
            if(!ch[u][id]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][id] = sz++;
            }
            u = ch[u][id];
        }
        val[u] = v;
    }
    void print(int j, int pos) {
        while(j) {
            if(val[j]) {
                int st = pos - len[val[j]] + 1;
                ban[st] = max(ban[st], len[val[j]]);
            }
            j = last[j];
        }
    }
    void find(const char *T) {
        int j = 0, res = 0;
        for(int i = 0; T[i]; ++i) {
            int c = idx(T[i]);
            j = ch[j];
            print(j, i);
        }
    }
    void getFail() {
        queue<int> qu;
        f[0] = 0;
        for(int c = 0; c < sigma_size; ++c) {
            int u = ch[0];
            if(u) { f[u] = 0; qu.push(u); last[u] = 0; }
        }
        while(!qu.empty()) {
            int r = qu.front(); qu.pop();
            for(int c = 0; c < sigma_size; ++c) {
                int u = ch[r];
                if(!u) { ch[r] = ch[f[r]]; continue; }
                qu.push(u);
                int v = f[r];
                while(v && !ch[v]) v = f[v];
                f[u] = ch[v];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }
}ac;



int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        ac.clear();
        for(int i = 1; i <= N; ++i) {
            scanf("%s", s);
            len[i] = strlen(s);
            for(int j = 0; j < len[i]; ++j)
                s[i] = tolower(s[i]);
            ac.insert(s, i);
        }
        ac.getFail();
        gets(s); gets(s);
        Len = strlen(s);
        for(int i = 0; i < Len; ++i) {
            if(isalpha(s[i])) t[i] = tolower(s[i]);
            else t[i] = 'a' + 26;
        }
        t[Len] = 0;
        memset(ban, 0, sizeof(ban));
        ac.find(t);
        int R = -1;
        for(int i = 0; i < Len; ++i) {
            R = max(R, i + ban[i] - 1);
            if(i <= R) putchar('*');
            else putchar(s[i]);
        }
        puts("");
    }
    return 0;
}