题目链接

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
 
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[];
int v[];
int head,tail; struct node
{
node *fail;
node *next[];
int count;
node()
{
fail=NULL;
count=;
for(short i=;i<;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=;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=;i<;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=;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>)
{
v[i-temp->count+]++;
v[i+]--;
break;
}
temp=temp->fail;
}
}
return ;
} int main()
{
int T, num;
scanf("%d",&T);
while(T--)
{
for(int i=;i<tail;i++)
free(q[i]);
memset(v,,sizeof(v));
head=tail=;
root = new node();
scanf("%d", &num);
getchar();
for(int i=;i<num;i++)
{
gets(str);
insert(str);
}
setfail();
gets(str);
int len=strlen(str),sum=;
query();
for(int i=;i<len;i++)
{
sum+=v[i];
if(sum<=) printf("%c",str[i]);
else printf("*");
}
puts("");
}
return ;
}
 
 

最新文章

  1. c++聪聪看书(满分代码)
  2. [skill] 进程 线程
  3. Windows Store App 用户库文件操作
  4. [转]oracle 11g 忘记 默认用户密码
  5. jenkins+ant+ssh远程部署服务glassfish
  6. 如何获得iphone设备的剩余空间
  7. BZOJ 1798: [Ahoi2009]Seq 维护序列seq( 线段树 )
  8. IceMx.Mvc 我的js MVC 框架七、完善植物大战僵尸(增加阳光的消费和获得)
  9. MIT 计算机科学及编程导论 Python 笔记 1
  10. 【mock.js】后端不来过夜半,闲敲mock落灯花 ——南宋&#183;赵师秀
  11. 你必须知道的EntityFramework 6.x和EntityFramework Core变更追踪状态
  12. 什么是设计思维Design Thinking——风靡全球的创造力培养方法
  13. canvas和SVG
  14. [UE4]虚幻引擎的C++环境安装
  15. hadoop大数据基础框架技术详解
  16. 重新签名IOS .ipa文件 (包含第三方框架和插件)
  17. git pull文件时和本地文件冲突的问题
  18. mysql 5.1 下载地址 百度云网盘下载
  19. 【转】【Java/Android】Toast使用方法大全
  20. 使用VS2008进行WEB负载测试

热门文章

  1. struts2学习笔记之八:Action中方法的动态调用
  2. jQuery使用方法
  3. [Linux]Linux下安装和配置solr/tomcat/IK分词器 详细实例二.
  4. iOS-旧项目中手动内存管理(MRC)转ARC
  5. Eclipse 启动时提示“发现了以元素&#39;d:skin&#39;开头的无效内容,此处不应含有子元素“
  6. 第四章 HTML与JavaScript
  7. 前端学PHP之基础语法
  8. 【目录】Newlife XCode组件相关文章目录
  9. Eclipse快捷键(转)
  10. SQL Server安全(5/11):架构与安全(Schemas and Security)