首页 > 代码库 > 2016 年青岛网络赛---Family View(AC自动机)

2016 年青岛网络赛---Family View(AC自动机)

2024-08-14 01:57:17   223人阅读

题目链接

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
13trumprioDonald 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 1000005using 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;}

 

 
 

2016 年青岛网络赛---Family View(AC自动机)


联系
我们