字符串（AC自动机）：COCI 2015 round 5 divljak-白红宇

字符串（AC自动机）：COCI 2015 round 5 divljak

阅读量：4692 次

发布时间：2019-06-09

本文共 2029 字，大约阅读时间需要 6 分钟。

　　不用bit的话最大数据2.8s，超时，有些遗憾，代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int N=2000010; 8 int n,Q,cnt,len,x,tp,top,st[N],vis[N],tim; 9 int ch[N][26],fail[N],num[N],id[N];10 char s[N];queue
          
           q;11 int main(){12 freopen("divljak.in","r",stdin);13 freopen("divljak.out","w",stdout);14 ios::sync_with_stdio(false);15 cin.tie(NULL),cout.tie(NULL);16 cin>>n;17 for(int t=1;t<=n;t++){18 cin>>s;19 len=strlen(s);int p=0;20 for(int i=0;i
           
            >Q;37 while(Q--){38 cin>>tp;39 if(tp==1){40 cin>>s;top=0;41 len=strlen(s);int p=0;++tim;42 for(int i=0;i
            
             >x;52 cout<
             
              <<"\n";53 }54 }55 return 0;56 }

　　然后我的标解超时了？

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7 const int N=2000010;  8 int n,Q,cnt,len,x,tp,top,st[N];  9 int ch[N][26],fail[N],num[N],pd[N]; 10 int bit[N],fa[N][22],id[N],ed[N],tot; 11 int cntE,nxt[N],to[N],fir[N],dep[N]; 12 char s[N];queue
          
           q; 13 14 void addedge(int a,int b){ 15 nxt[++cntE]=fir[a]; 16 to[fir[a]=cntE]=b; 17 } 18 19 void DFS(int x,int f){ 20 id[x]=++tot;dep[x]=dep[f]+1; 21 for(int i=fir[x];i;i=nxt[i]) 22 fa[to[i]][0]=x,DFS(to[i],x); 23 ed[x]=tot; 24 } 25 26 int Lca(int x,int y){ 27 if(dep[x]
           
            =0;i--) 30 if(d>>i&1)x=fa[x][i]; 31 for(int i=21;x!=y;i?i--:i) 32 if(fa[x][i]!=fa[y][i]||!i) 33 x=fa[x][i],y=fa[y][i]; 34 return x; 35 } 36 37 int Add(int x,int d){ 38 while(x
            
             >n; 61 for(int t=1;t<=n;t++){ 62 cin>>s; 63 len=strlen(s);int p=0; 64 for(int i=0;i
             
              >Q; 87 while(Q--){ 88 cin>>tp; 89 if(tp==1){ 90 cin>>s;top=0; 91 len=strlen(s);int p=0; 92 for(int i=0;i
              
               >x;108 cout<
               
                <<"\n";109 }110 }111 //cout<<1.0*clock()/CLOCKS_PER_SEC<<"\n";112 return 0;113 }