hdu5880 Family View
地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=5880
题目:
Family View
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2109 Accepted Submission(s): 445
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."
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).
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.
思路:
裸ac自动机题,走到一个节点看下有匹配的没,有的话用最长串的长度把位置标记一下,然后输出即可。
ac自动机中实际节点数并不需要开到27*1e6!!!数据并没那么大
只需开到27*1e5
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std; struct AC_auto
{
const static int LetterSize = ;
const static int TrieSize = * ( 1e5 + ); int tot,root,fail[TrieSize],end[TrieSize],next[TrieSize][LetterSize]; int newnode(void)
{
memset(next[tot],-,sizeof(next[tot]));
end[tot] = ;
return tot++;
} void init(void)
{
tot = ;
root = newnode();
} int getidx(char x)
{
if(x<='z'&&x>='a') return x - 'a';
if(x<='Z'&&x>='A') return x - 'A';
return ;
} void insert(char *ss)
{
int len = strlen(ss);
int now = root;
for(int i = ; i < len; i++)
{
int idx = getidx(ss[i]);
if(next[now][idx] == -)
next[now][idx] = newnode();
now = next[now][idx];
}
end[now] = len;
} void build(void)
{
queue<int>Q;
fail[root] = root;
for(int i = ; i < LetterSize; i++)
if(next[root][i] == -)
next[root][i] = root;
else
fail[next[root][i]] = root,Q.push(next[root][i]);
while(Q.size())
{
int now = Q.front();Q.pop();
for(int i = ; i < LetterSize; i++)
if(next[now][i] == -) next[now][i] = next[fail[now]][i];
else
fail[next[now][i]] = next[fail[now]][i],Q.push(next[now][i]);
}
} void match(char *ss,int *cnt)
{
int len,now;
len = strlen(ss),now = root;
for(int i = ; i < len; i++)
{
int idx = getidx(ss[i]);
int tmp = now = next[now][idx], ret = ;
while(tmp)
{
ret = max( ret, end[tmp]);
tmp = fail[tmp];
}
if(ret)
cnt[i-ret+]++,cnt[i+]--;
}
}
void debug()
{
for(int i = ;i < tot;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j = ;j < LetterSize;j++)
printf("%3d",next[i][j]);
printf("]\n");
}
}
}ac; char ss[];
int cnt[]; int main(void)
{
int t,n;
scanf("%d",&t);
while(t--)
{
ac.init();
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%s",ss),ac.insert(ss);
getchar(),gets(ss);
ac.build();
ac.match(ss,cnt);
for(int i=,ret=,len=strlen(ss);i<len;i++)
{
ret+=cnt[i],cnt[i]=;
if(ret>) ss[i]='*';
}
printf("%s\n",ss);
}
return ;
}
最新文章
- android 之httpclient方式提交数据
- 详解Java GC的工作原理+Minor GC、FullGC
- JavaScript 控制字体大小设置
- [马哥学习笔记]Linux系统裁剪之制作带网络功能的可启动linux
- Android开发学习之路-回调实现Service向activity传递数据
- python zookeeeper 学习和操作
- pandas 练习
- 使用AmplifyJS和JQuery编写更好更优雅的javascript事件处理代码
- input file样式修改,图片预览删除功能
- spark System memory must be at least
- C#基础知识之关键字
- mysql安装完启动问题解决
- vue版 文件下载
- linux硬盘的分区、格式化、挂载以及LVM
- BZOJ3944 Sum 数论 杜教筛
- mips体系堆栈回溯分析与实现
- lua -- 在弹框中显示物品列表
- SonarQube配置LDAP认证集成
- CentOS 7 Install Redis
- linux的文件类型和权限