哪个学校设有网站开发专业,用网站的源代码怎么做网站,app制作开发费用多少,传奇176网页游戏敏感词汇 发布时间: 2017年7月5日 00:23 最后更新: 2017年7月6日 14:40 时间限制: 1500ms 内存限制: 128M 描述 我们知道#xff0c;在进行聊天时#xff0c;有些词汇是敏感词汇#xff0c;含有敏感词汇的内容是不允许被发送的。现在给定m个敏感词汇#xff0c;并给定… 敏感词汇 发布时间: 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 1e67;
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()
{queueint 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);}
}
