Type: AC自动机
题意
给你N个子串,一个主串,让你过滤掉在主串中出现过的子串.被过滤掉的用*表示
每个子串是由小写字母组成
题解
AC自动机,一开始被两个样例卡住了
1- 子串: abcd bc 主串: abcef 匹配不到 bc
2- 子串: a ab abc abcd 主串: aabcd 匹配不到 abcd第一种情况是因为当你遍历到abcd这条路径的c节点时,如果因为下一个是f就判断为失配并且不继续向下走,则就无法再匹配到bc.
解决方法,在每次判断到失配的时候,新开一个函数从开始失配的节点 这里是 c ,从这个节点开始找他的失陪路径,知道找到 第一个尾节点 或 根节点 就停止,目标串即为最长被匹配串,不需要再去匹配他的子串了.
第二种情况是因为一开始写代码每次循环时直接将u查找到了根节点,所以如果一个子串前面是另一个串的子串,那么将永远无法匹配到另一个子串.
解决方法,不改动u,借助临时变量来更改u达到查找子串的目的.
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+6;
int T,N,tot_len;
char str[maxn],len[maxn];
struct AC_AutoMaton{
static const int sigma_size=26;
int ch[maxn][sigma_size];
int f[maxn];
int cle[maxn],val[maxn];
int siz,root;
int newNode(){
for(int i=0;i<sigma_size;++i){
ch[siz][i]=0;
}
f[siz]=val[siz]=0;
return siz++;
}
void init(){
for(int i=0;i<maxn;++i) val[i]=0;
siz=0;root=0;
newNode();
}
int ord(char c){
if(isupper(c))
c=tolower(c);
return (int)(c-'a');
}
void insert(char *s,int v){
int u=root,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=newNode();
u=ch[u][c];
}
val[u]=v;
}
void getFail(){
queue<int> Q;
Q.push(root);
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
if(ch[k][c]){
f[ch[k][c]]=k?ch[f[k]][c]:0;
Q.push(ch[k][c]);
}
else ch[k][c]=ch[f[k]][c];
}
}
}
void add(int u,int i){
while(u){
if(val[u]){
int t=len[val[u]];
for(int r=0;r<t;++r){
cle[i-r]=1;
}
return;
}
u=f[u];
}
}
void Find(char *s){
int u=0,n=tot_len;
for(int i=0;i<tot_len;++i) cle[i]=0;
for(int i=0;i<n;++i){
if(!isalpha(s[i])){
u=0;
continue;
}
int c=ord(s[i]);
///下面这句加不加都一样
//while(u && !ch[u][c]) u=f[u];
u=ch[u][c];
/*
int p=u;
//cout<<i<<" "<<u<<": "<<c<<endl;
///while是用来判断子串的.这道题不需要加
while(p && val[p]){
p=f[p];
}
*/
add(u,i);
}
}
void print(){
for(int i=0;i<tot_len;++i){
if(cle[i]) putchar('*');
else putchar(str[i]);
}
printf("\n");
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str);
aho.insert(str,i+1);
len[i+1]=strlen(str);
}
getchar();
aho.getFail();
tot_len=0;
//scanf("%[^\n]",str);
gets(str);
tot_len=strlen(str);
//cout<<tot_len<<endl;
aho.Find(str);
aho.print();
}
return 0;
}