博客

BUG传送门：布呗之路

/**
题址：https://vjudge.net/problem/HDU-5880

题意：给出一些敏感词(大小写不敏感)，用'*'替代敏感词

分析：多模匹配问题，AC自动机，插入时不断更新最长后缀，最后用vis扫描一遍输出即可；
 
具体细节看代码标注 ，G++容易超时，交题的时候尽量选择C++ 
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstdio>
#include <cstring>
#define  ll long long
#define  ull unsigned long long
#define  max(a,b) a>b?a:b
#define  min(a,b) a>b?b:a
#define  PI acos(-1.0)
#define  inf 0x3f3f3f3f
#define  E 2.7182818284590452353602874713527
using namespace std;

const int maxn=1e6+7,max_cnt=26;
int q[maxn],vis[maxn];
char buf[maxn];
int num;

struct node{
    int fail,Next[max_cnt];
    int id,len;
    void init() {
        fail=-1;
        for(int i=0;i<max_cnt;i++) Next[i]=-1;
        id=len=0;
    }
}a[maxn];

void Insert(char buf[]) {
    int now=0;
    int len=strlen(buf);
    for (int i=0;i<len;i++) {
        if (a[now].Next[buf[i]-'a']==-1) {
            a[now].Next[buf[i]-'a']=++num;
            a[num].init();
        }
        now=a[now].Next[buf[i]-'a'];
    }
    a[now].id++;
    a[now].len=max(a[now].len,len);//更新以该节点为结束的字符串的最长长度 
}

void AC_build() {
    queue<int>Q;
    int now=0,root=0;
    for (int i=0;i<max_cnt;i++) {
        if (a[now].Next[i]!=-1) {
            a[a[now].Next[i]].fail=root;
            Q.push(a[now].Next[i]);//将已经存在的边放入队列中，方便在对fail指针进行操作，类似于一个初始化； 
        } else a[now].Next[i]=root;
    }
    while (!Q.empty()) {
        int p=Q.front();
        Q.pop();
        for (int i=0;i<max_cnt;i++) {
            if (a[p].Next[i]==-1) a[p].Next[i]=a[a[p].fail].Next[i];
            else {
                a[a[p].Next[i]].fail=a[a[p].fail].Next[i];
                Q.push(a[p].Next[i]);
            }
        }
    }
}

void Search(string s) {
    int p=0,k=0,root=0;
    int len=s.size();
    for (int i=0;i<len;i++) { 
        if (s[i]>='a'&&s[i]<='z') p=a[p].Next[s[i]-'a'];
        else {
		//只对字母敏感，其余直接返回即可
            p=root;
            continue;
        }
        /**
        vis记录标注敏感词的区间，利用非非负性对原串进行选择性的输出 
		*/ 
        int now=p; 
        while (now!=root&&a[now].id!=-1) {
            if (a[now].id) {
                vis[i-a[now].len+1]++;
                vis[i+1]--; 
            }
            now=a[now].fail;
        }
    }
}

int main() {
    num=0;
    string s,temp;
    int t;
    scanf("%d",&t);
    while(t--) {
        int n,len;
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        num=0;
        a[0].init();
        for (int i=1;i<=n;i++) {
            scanf("%s",buf);
            Insert(buf);
        }
        getchar();
        getline(cin,s); 
        len=s.length();
        temp=s;
        for (int i=0;i<len;i++) {
            if (s[i]>='A'&&s[i]<='Z') s[i]+=32;
        }
        AC_build();
        Search(s);
        int sum=0;
        for (int i=0;i<len;i++) {
            sum+=vis[i];
            if (sum>0) printf("*");
            else printf("%c",temp[i]);
        }
        printf("\n");
    }
    return 0;
}