首页 > 代码库 > hdu5880 （AC自动机）
hdu5880 （AC自动机）
题目链接：hdu5880 Family View
题意：敏感词屏蔽，给一堆敏感词，给一段文本，要求把文本中所有的敏感词用*代替。
题解：对敏感词建出AC自动机，在AC自动机上跑文本，就可以得到文本的每个前缀的最长匹配后缀，扫一遍即可得到结果。
弱弱的说我还不会用AC自动机啊，赛后补题先留下大神的模板吧。。。
再留个博客改天练练：http://www.cnblogs.com/kuangbin/p/3164106.html
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<queue> 6 #define CLR(a,b) memset((a),(b),sizeof((a))) 7 using namespace std; 8 const int N = 1000010; 9 int d[N]; 10 int ans[N]; 11 struct Trie{ 12 int next[N][26],fail[N],end[N]; 13 int root,L; 14 int newnode(){ 15 for(int i = 0;i < 26;i++) 16 next[L][i] = -1; 17 end[L++] = 0; 18 return L-1; 19 } 20 void init(){ 21 L = 0; 22 root = newnode(); 23 } 24 void insert(char buf[]){ 25 int len = strlen(buf); 26 int now = root; 27 for(int i = 0;i < len;i++){ 28 if(next[now][buf[i]-‘a‘] == -1) 29 next[now][buf[i]-‘a‘] = newnode(); 30 now = next[now][buf[i]-‘a‘]; 31 } 32 end[now] = 1; 33 d[now] = len; 34 } 35 void build(){ 36 queue<int>Q; 37 fail[root] = root; 38 for(int i = 0;i < 26;i++) 39 if(next[root][i] == -1) 40 next[root][i] = root; 41 else{ 42 fail[next[root][i]] = root; 43 Q.push(next[root][i]); 44 } 45 while( !Q.empty() ){ 46 int now = Q.front(); Q.pop(); 47 for(int i = 0;i < 26;i++) 48 if(next[now][i] == -1) 49 next[now][i] = next[fail[now]][i]; 50 else{ 51 fail[next[now][i]] = next[fail[now]][i]; 52 Q.push(next[now][i]); 53 } 54 } 55 } 56 void solve(char buf[]){ 57 int cur = root; 58 int len = strlen(buf); 59 int index; 60 for(int i = 0; i < len ; ++i){ 61 if(buf[i] >= ‘A‘ && buf[i] <= ‘Z‘) 62 index = buf[i] - ‘A‘; 63 else if(buf[i] >= ‘a‘ && buf[i] <= ‘z‘) 64 index = buf[i] - ‘a‘; 65 else continue; 66 cur = next[cur][index]; 67 int x = cur; 68 while(x != root){ 69 if(end[x]){ 70 ans[i + 1] -= 1; 71 ans[i - d[x] + 1] += 1; 72 break; 73 } 74 x = fail[x]; 75 } 76 } 77 } 78 }; 79 char buf[N]; 80 Trie ac; 81 int main(){ 82 int T, i, n, len; 83 scanf("%d", &T); 84 while( T-- ){ 85 scanf("%d", &n); 86 ac.init(); 87 for(int i = 0;i < n;i++){ 88 scanf("%s", buf); 89 ac.insert(buf); 90 } 91 getchar(); 92 ac.build(); 93 gets(buf); 94 //scanf("%s", buf); 95 CLR(ans, 0); 96 ac.solve(buf); 97 long long res = 0; 98 len = strlen(buf); 99 for(i = 0; i < len; ++i){100 res += ans[i];101 if(res <= 0)102 printf("%c", buf[i]);103 else printf("*");104 }105 puts("");106 }107 return 0;108 }
hdu5880 （AC自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。