JZYZOJ1369 [coci2012]覆盖字符串 AC自动机

时间:2021-11-21 18:09:37

http://172.20.6.3/Problem_Show.asp?id=1369

trie树如果不优化就这么往里面放这么多单词肯定超空间+超时,所以需要去掉无用的字符串(不属于原字符串的),但是一个一个判断时间又很长;

所以解决方案就是用一个多维vis数组胡搞判定一下,非常魔性。。。

代码

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const long long maxn=;
const int modn=;
int n,m;
char ch[maxn]={};
char ch1[]={};
int vis[maxn]={};
queue<int>q;
struct trie{
int next[];
bool exist;
int fail,d;
}e[maxn*];int tot=;
bool ff[][][][][]={};
void insert(int k,int d,int x){
if(d==k){
e[x].exist=;e[x].d=d;
return;
}
int z=ch1[d]-'a';
if(!e[x].next[z])e[x].next[z]=++tot;
insert(k,d+,e[x].next[z]);
}
void build(){
q.push();int x,y,f;
while(!q.empty()){
x=q.front();q.pop();
for(int i=;i<;i++){
y=e[x].next[i];
if(y){
if(x!=){
f=e[x].fail;
while((!e[f].next[i])&&f)f=e[f].fail;
e[y].fail=e[f].next[i];
}q.push(y);
}
}
}
}
int read(){
char chh=getchar();int k=;
while(chh<'a'||chh>'z'){chh=getchar();}
while(chh>='a'&&chh<='z'){ch1[k++]=chh;chh=getchar();}
return k;
}
void read1(){
char chh=getchar();int k=;
while(chh<'a'||chh>'z'){chh=getchar();}
while(chh>='a'&&chh<='z'){ch[k++]=chh;chh=getchar();}
}
int main(){
//freopen("wtf.in","r",stdin);
//freopen("wtf.out","w",stdout);
scanf("%d",&n);read1();
for(int i=;i<n;i++){
ff[(int)ch[i-]-'a'][(int)ch[i-]-'a'][(int)ch[i-]-'a'][(int)ch[i-]-'a'][(int)ch[i]-'a']=;
}
scanf("%d",&m);
for(int i=;i<=m;i++){
int siz=read(),wtf=;
for(int j=;j<siz;j++){
if(!ff[(int)ch1[j-]-'a'][(int)ch1[j-]-'a'][(int)ch1[j-]-'a'][(int)ch1[j-]-'a'][(int)ch1[j]-'a'])
wtf=;
}if(wtf)insert(siz,,);
}build();
int x=,y;
for(int i=;i<n;i++){
int z=ch[i]-'a';
while((!e[x].next[z])&&x){
x=e[x].fail;
}
x=e[x].next[z];y=x;
while((!e[y].exist)&&y){
y=e[y].fail;
}vis[i-e[y].d+]=max(vis[i-e[y].d+],e[y].d);
}
int k=;int t=;
for(int i=;i<n;i++){
k=max(vis[i],k);
if(k>)t++;
k--;
}
printf("%d\n",n-t);
return ;
}