2016 年青島網絡賽---Family View(AC自動機)，2016---family

2016 年青島網絡賽---Family View(AC自動機)，2016---family

題目鏈接

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

 

Problem Description 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."   Input The first line contains the number of test cases. For each test case:
The first line contains an integer n, represneting the size of the forbidden words list P. Each line of the next n lines contains a forbidden words Pi (1≤|Pi|≤1000000,∑|Pi|≤1000000) where Pi only contains lowercase letters.

The last line contains a string T (|T|≤1000000).   Output For each case output the sentence in a line.   Sample Input 1 3 trump ri o Donald John Trump (born June 14, 1946) is an American businessman, television personality, author, politician, and the Republican Party nominee for President of the United States in the 2016 election. He is chairman of The Trump Organization, which is the principal holding company for his real estate ventures and other business interests.   Sample Output D*nald J*hn ***** (b*rn June 14, 1946) is an Ame**can businessman, televisi*n pers*nality, auth*r, p*litician, and the Republican Party n*minee f*r President *f the United States in the 2016 electi*n. He is chairman *f The ***** *rganizati*n, which is the p**ncipal h*lding c*mpany f*r his real estate ventures and *ther business interests.   Source 2016 ACM/ICPC Asia Regional Qingdao Online  

 

Recommend wange2014   |   We have carefully selected several similar problems for you:  5901 5899 5898 5897 5896    題意：有n個由小寫字母構成的敏感詞，現在給了一個主串，要求將其中出現的敏感詞由“ * ” 代替 然後輸出這個主串；   思路：套用AC自動機模板，較快的處理方法是定義一個標記數組v[maxn] ，在主串中出現敏感詞的開始位置v[start]++,結束位置v[end+1]--   最後在對主串輸出時，sum+=v[i], 如果sum>0 輸出“*” 否則輸出字符。   這題數據較大，很多人都一直爆內存，我也是~  我在建立trie樹的時候用的鏈表，那麼每次插入新的節點時都開了一個節點的空間，每組數據算完後沒有清理這些空間，所以不管怎麼改一直爆內存，後來才發現，唉！  所以一定要注意清空內存哦！   代碼如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 1000005
using namespace std;
char str[1000005];
int v[1000005];
int head,tail;

struct node
{
    node *fail;
    node *next[26];
    int count;
    node()
    {
        fail=NULL;
        count=0;
        for(short i=0;i<26;i++)
        next[i]=NULL;
    }
}*q[N];
node *root;
void insert(char *str) ///建立Trie
{
    int temp,len;
    node *p=root;
    len=strlen(str);
    for(int i=0;i<len;i++)
    {
        temp=str[i]-'a';
        if(p->next[temp]==NULL)
           p->next[temp]=new node();
        p=p->next[temp];
    }
    p->count=len;
}
void setfail() ///初始化fail指針，BFS
{
    q[tail++]=root;
    while(head!=tail)
    {
        node *p=q[head++];
        node *temp=NULL;
        for(short i=0;i<26;i++)
        if(p->next[i]!=NULL)
        {
            if(p==root) ///首字母的fail必指向根
            p->next[i]->fail=root;
            else
            {
                temp=p->fail; ///失敗指針
                while(temp!=NULL) ///2種情況結束：匹配為空or找到匹配
                {
                    if(temp->next[i]!=NULL) ///找到匹配
                    {
                        p->next[i]->fail=temp->next[i];
                        break;
                    }
                    temp=temp->fail;
                }
                if(temp==NULL) ///為空則從頭匹配
                    p->next[i]->fail=root;
                }
            q[tail++]=p->next[i]; ///入隊;
        }
    }
}

void query()
{
    node *p=root;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int index;
        if(str[i]>='A'&&str[i]<='Z') index=str[i]-'A';
        else if(str[i]>='a'&&str[i]<='z')  index=str[i]-'a';
        else { p=root; continue; }
        while(p->next[index]==NULL&&p!=root) ///跳轉失敗指針
        p=p->fail;
        p=p->next[index];
        if(p==NULL)
        p=root;
        node *temp=p; ///p不動，temp計算後綴串
        while(temp!=root)
        {
            if(temp->count>0)
            {
                v[i-temp->count+1]++;
                v[i+1]--;
                break;
            }
            temp=temp->fail;
        }
    }
    return ;
}

int main()
{
    int T, num;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<tail;i++)
            free(q[i]);
        memset(v,0,sizeof(v));
        head=tail=0;
        root = new node();
        scanf("%d", &num);
        getchar();
        for(int i=0;i<num;i++)
        {
            gets(str);
            insert(str);
        }
        setfail();
        gets(str);
        int len=strlen(str),sum=0;
        query();
        for(int i=0;i<len;i++)
        {
            sum+=v[i];
            if(sum<=0) printf("%c",str[i]);
            else printf("*");
        }
        puts("");
    }
    return 0;
}