2016 年青岛网络赛---Family View(AC自动机)
2018-06-17 23:45:39来源:未知 阅读 ()
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5880
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).
#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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架:gevent 2020-06-05
- 2020年3月28日UCF Local Programming Contest 2016 2020-03-31
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- 【新年呈献】高性能网络通信框架 HP-Socket v5.7.1 2020-01-07
- 最小割最大流定理&残量网络的性质 2019-12-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash