这题简直比注水猪肉还水QAQ。
以前做过KMP的Censoring单串匹配，果断选择自动AC机w
对短串建自动AC机
长串去机子里匹配
用个栈边匹配边弹出
记得弹出一个串后把匹配点指向栈顶就ojbk
（话说自动AC机也不能自动AC QAQ）
#include<cmath>
#include<queue>
#include<cstdio>
#define Zs 13331
#include<cstring>
#include<iostream>
#define QAQ 100100
#include<algorithm>
#define ull unsigned long long
using namespace std;
struct node{
int c;
int num;
node *f;
node *ch[];
node(){
c=,f=NULL;num=;
memset(ch,NULL,sizeof ch);
}
}*last[QAQ];
int n;
char s[][QAQ];
char stack[QAQ];int top=;
node *root=new node();
inline void insert(int id){
node *p=root;int i=,index;
while(s[id][i]){
index=s[id][i]-'a';
if(p->ch[index]==NULL)p->ch[index]=new node();
p=p->ch[index];
++i;
}
p->num=strlen(s[id]+);
}
void GetFail(){
queue<node*>qwq;
for(int i=;i<;i++){
if(root->ch[i]!=NULL)
root->ch[i]->f=root,
qwq.push(root->ch[i]);
else root->ch[i]=root;
}
while(!qwq.empty()){
node *now=qwq.front();qwq.pop();
for(int i=;i<;i++){
if(now->ch[i]!=NULL)
now->ch[i]->f=now->f->ch[i],
qwq.push(now->ch[i]);
else now->ch[i]=now->f->ch[i];
}
}
}
void query(char *s){
node *now=root;int i=;
while(s[i]){
stack[++top]=s[i];
if(now==NULL)now=root;last[top]=now;
now=now->ch[s[i]-'a'];
for(node *j=now;j!=NULL&&j!=root;j=j->f){
int out=j->num;
if(j->f!=NULL&&!j->f->num)j->f=j->f->f;
if(!out)continue;
top-=out;
now=last[top+];
break;
}
++i;
}
}
void puts_out(){
for(int i=;i<=top;i++){
printf("%c",stack[i]);
}
}
int main(){
// freopen("cen .in","r",stdin);
// freopen("cen.out","w",stdout);
scanf("%s",s[]+);
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",s[i]+);
insert(i);
}
GetFail();
query(s[]);
puts_out();
}
丑比代码QAQ
哦还有，这个啥玩意儿Trie图挺闹心的，还得优化
留坑待填QwQ （waiting......）