2017西安交大ACM小学期 敏感词汇[AC自动机]

敏感词汇

发布时间: 2017年7月5日 00:23   最后更新: 2017年7月6日 14:40   时间限制: 1500ms   内存限制: 128M

描述

我们知道，在进行聊天时，有些词汇是敏感词汇，含有敏感词汇的内容是不允许被发送的。现在给定m个敏感词汇，并给定一段文本，请将所有敏感词汇都用星号替换掉。

输入

包含多组数据。
每组数据第一行一个正整数m，表示有m个敏感词汇。
接下来m行每行一个敏感词汇，敏感词汇仅包含小写字母。
最后一行为文本，仅包含小写字母。
每组数据保证敏感词汇总长度不超过106，文本不超过106。
总字符输入量不超过107。

输出

对每组数据，输出一行一个字符串，表示敏感词汇都用星号替换掉后的文本。

样例输入1 复制 3 naive simple glasses glassesimplenaiveexcited 样例输出1 *****************excited

这是一个比较裸的AC自动机的题

这里要注意几点：

1.不能边检测边覆盖，不然肯定会超时，所以我们用一个replace数组记录下从当前这个位置应该向前覆盖*的个数

2.在检测到下一个字符，并且往前回溯的时候，只要搜索到第一个有效模式即可，因为剩下的模式长度只能更小，我们覆盖大模式的时候，肯定就可以覆盖掉小的模式

3.最后覆盖的时候，从后往前扫描replace数组，可以在O(n)时间内完成覆盖

代码：

#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN = 1e6+7; int replace[MAXN]; #define LETTER 26 struct Trie{int num, fail,match;int next[LETTER];int dep; }pool[MAXN]; Trie* const trie = pool + 1; int cnt; void init(){cnt = 0;memset(pool, 0, 2 * sizeof(Trie));trie[0].fail = -1; } inline int convert(char c){return c - 'a'; } void build() {queue<int> q; q.push(0);while (!q.empty()){int t = q.front(); q.pop();for (int i = 0; i < LETTER; i++){int &cur = trie[t].next[i];if (cur){q.push(cur);trie[cur].fail = trie[trie[t].fail].next[i];trie[cur].match = trie[cur].num ? cur :trie[trie[cur].fail].match;}else cur = trie[trie[t].fail].next[i];}} } int search(char *s) {int ret = 0, cur = 0;for (int i = 0; s[i]; i++){cur = trie[cur].next[convert(s[i])];for (int temp = trie[cur].match; temp;temp = trie[trie[temp].fail].match){//ret += trie[temp].num;if(trie[temp].num){replace[i] = trie[temp].dep;break;}//trie[temp].num = 0;}}return ret; } void insert(char s[]){int cur = 0;for(int i = 0;s[i];i++){int &pos = trie[cur].next[convert(s[i])];if(!pos){pos = ++cnt;memset(&trie[cnt],0,sizeof(Trie));}trie[pos].dep = trie[cur].dep + 1;cur = pos;}trie[cur].num ++; }char pat[MAXN]; char str[MAXN]; int main(){int m;while(~scanf("%d",&m)){init();memset(replace,0,sizeof(replace));while(m--){scanf(" %s",pat);insert(pat);}build();scanf(" %s",str);int ans = search(str);//printf("%d\n",ans);int len = strlen(str);int cnt = 0;for(int i = len-1;i >= 0;i--){cnt = max(cnt,replace[i]);if(cnt){str[i] = '*';cnt--;}}puts(str);} }

总结

以上是生活随笔为你收集整理的2017西安交大ACM小学期 敏感词汇[AC自动机]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。