1. 首页
2. AC自动机
3. 本页

HDU 5880 Family View (AC自动机)

题目链接：点我~~

题意：敏感词屏蔽，给一堆敏感词，给一段文本，要求把文本中所有的敏感词用*代替。

思路：对敏感词建出AC自动机，在AC自动机上跑文本，可以得到每个前缀的最长匹配后缀，再将每一匹配到的段标记，最后再扫一遍输出。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 1000100;

int cnt[MAXN],vis[MAXN];

struct Trie
{
    int next[MAXN][26],fail[MAXN],end[MAXN];
    int root,L;
    int newnode()
    {
        for(int i = 0; i < 26; i++)
            next[L][i] = -1;
        end[L++] = 0;
        return L-1;
    }
    void init()
    {
        L = 0;
        root = newnode();
    }
    void insert(char buf[])
    {
        int len = strlen(buf);
        int now = root;
        for(int i = 0; i < len; i++)
        {
            if(next[now][buf[i]-'a'] == -1)
                next[now][buf[i]-'a'] = newnode();
            now = next[now][buf[i]-'a'];
        }
        end[now]=1;  //trie树匹配节点标记
        cnt[now]=len;
    }
    void build()
    {
        queue<int>Q;
        fail[root] = root;
        for(int i = 0; i < 26; i++)
            if(next[root][i] == -1)
                next[root][i] = root;
            else
            {
                fail[next[root][i]] = root;
                Q.push(next[root][i]);
            }
        while( !Q.empty() )
        {
            int now = Q.front();
            Q.pop();
            for(int i = 0; i < 26; i++)
                if(next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }
    }
    void query(char buf[])
    {
        int len = strlen(buf);
        int now = root;
        int res = 0;
        for(int i = 0; i < len; i++)
        {
            if(buf[i]>='a' && buf[i]<='z')
                now = next[now][buf[i]-'a'];
            else if(buf[i]>='A' && buf[i]<='Z')
                now = next[now][buf[i]-'A'];
            else
                continue;
            int temp = now;
            while( temp != root )
            {
                if(end[temp])
                {
                    vis[i+1]-=1;
                    vis[i-cnt[temp]+1]+=1;
                }
                temp = fail[temp];
            }
        }
        return ;
    }
};

char buf[MAXN];
int pos[MAXN];
Trie ac;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        //memset(cnt,0,sizeof(cnt));
        ac.init();
        for(int i = 0; i < n; i++)
        {
            scanf("%s",buf);
            ac.insert(buf);
        }
        getchar();
        ac.build();
        gets(buf);
        ac.query(buf);
        int ans=0;
        int len=strlen(buf);
        for(int i=0; i<len; ++i)
        {
            ans+=vis[i];
            if(ans<=0)
                printf("%c",buf[i]);
            else
                printf("*");
        }
        puts("");
    }
    return 0;
}