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

编程爱好者联盟

2016-09-20

题目链接

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

; ;<div>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

; ;<div>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;
}

; ; ; ;

mathjax

安科网

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

编程爱好者联盟

编程爱好者联盟

相关推荐

在Fedora上搭建Jupyter和数据科学环境

Python:线性代数-LaTeX用法(四十)

MathJax: 让前端支持数学公式

Hexo搭建GitHub博客—打造炫酷的NexT主题--高级(四)

html5 canvas作的手写板【兼容手机】

Linux下优秀的文本编辑器（Markdown、LaTeX、MathJax）

详解如何让InstantClick兼容MathJax、百度统计等

神经网络算法

Nginx对fastcgi的配置

TensorFlow学习之运行label_image实例

Apache重写去除入口文件index.php

MarkDown 插入数学公式实验大集合

编程爱好者联盟