HDU - 5880 Family View (AC自动机修改母串)
程序员文章站
2022-06-19 09:25:12
Family View (AC自动机修改母串)题目大意:给出一些敏感词,如果在文章中出现的话,用 ‘ * ’ 替代。解题思路:多模式串匹配问题,在建立字典树的时候标记一下敏感词结尾和长度,然后用主串匹配的时候碰到敏感词就用 ‘ * ’ 替换即可。Code:#include #include #include #include #include ...
Family View (AC自动机修改母串)
题目大意:给出一些敏感词,如果在文章中出现的话,用 ‘ * ’ 替代。
解题思路:多模式串匹配问题,在建立字典树的时候标记一下敏感词结尾和长度,然后用主串匹配的时候碰到敏感词就用 ‘ * ’ 替换即可。
Code:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define INT 9654234
using namespace std;
const int maxn = 1000010;
struct Trie{
int next[maxn][26],fail[maxn],end[maxn],size[maxn];
int root,l;
int newnode(){
for(int i=0;i<26;i++) next[l][i]=-1;
end[l++]=0;
return l-1;
}
void init(){
l=0;
memset(size,0,sizeof size);
root =newnode();
}
void insert(char buf[]){
int len=strlen(buf);
int now=root;
for(int i=0;i<len;i++){
if(next[now][buf[i]-'a']==-1)
next[now][buf[i]-'a']=newnode();
now=next[now][buf[i]-'a'];
}
size[now]=len; //记录下敏感词结尾以及长度
}
void bulid(){
queue<int> q;
fail[root]=root;
for(int i=0;i<26;i++){
if(next[root][i]==-1) next[root][i]=root;
else {
fail[next[root][i]]=root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now= q.front();
q.pop();
for(int i=0;i<26;i++){
if(next[now][i]==-1) next[now][i]=next[fail[now]][i];
else{
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
void query(char buf[]){
int len=strlen(buf);
int now=root;
int res=0;
for(int i=0;i<len;i++){
///////////////////////////////////////////////////////////////////////
now=next[now][tolower(buf[i])-'a']; //tolower大写字母转化成小写
for(int tmp=now;tmp;tmp=fail[tmp]){
if(size[tmp]){ //找到敏感词,用 * 代替
for(int k=i;k>i-size[tmp];k--){
buf[k]='*';
}
}
}
////////////////////////////////////////////////////////////////////////
}
}
} ac;
char buf[maxn<<1];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T,n;
cin>>T;
while(T--){
cin>>n;
ac.init();
for(int i=1;i<=n;i++){
cin>>buf;
ac.insert(buf);
}
ac.bulid();
// getline(cin,buf);
char ch;
while(ch=getchar()!='\n'); //gets读入一行
gets(buf);
int len=strlen(buf);
ac.query(buf);
// cout<<buf<<endl;
puts(buf);
}
return 0;
}
本文地址:https://blog.csdn.net/weixin_43872264/article/details/107624160
上一篇: 选购家用打印机的四个小TIPS
下一篇: 天猫精灵指示灯颜色怎么自定义设置?