HDU - 5880 Family View (AC自动机修改母串)

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