#include  < iostream >
#include 
< queue >

using   namespace  std;

#define  N 100010

char  str[N], s[N][ 7 ];
int   d[N], pos[N], n, cnt1[N], cnt2[N];

struct  Trie{
    
int  idx, fail;
    
char  level;
    Trie
*  next[ 26 ],  * prefix;
    
void  init(){ 
        idx
=   - 1 , prefix =   0 ; level =   - 1 ; fail =   - 1 ;
        
for int  i =   0 ; i <   26 ++ i ) next[i] =   0 ; }
}tb[
800000 ],  * root;

int  sz;
void  init(){
    sz
=   0 ; root =  tb; root -> init();
    
for int  i =   0 ; i <=  n;  ++ i ){
        pos[i]
=   - 1 ; cnt1[i] =   0 ; cnt2[i] =   0 ; }
}

void  insert(  char *  s,  int  cnt ){
    Trie
*  r =  root;
    
for ( ;  * s; s ++  ){
        
int  t =   * s -   ' a ' ;
        
if ! r -> next[t] ){
            
++ sz; tb[sz].init(); tb[sz].level =  r -> level +   1 ;
            r
-> next[t] =  tb +  sz;
        }
        r
=  r -> next[t];
    }
    
if ( r -> idx ==   - 1  ) r -> idx =  cnt;
    r
-> fail =  r -> idx;
}

int  search(  char *  s ){
    Trie
*  r =  root;
    
for ( ;  * s; s ++  ){
        
int  t =   * s -   ' a ' ;
        
if ! r )  return   - 1 ;
        r
=  r -> next[t];
    }
    
return  r -> idx; }

void  prefix(){
    queue
< Trie *>  q; q.push( root );
    Trie
*  p,  * tp;
    
while ! q.empty() ){
        p
=  q.front(); q.pop();
        
for int  t =   0 ; t <   26 ++ t )
        
if ( p -> next[t] ){
            tp
=  p -> prefix;
            
while ( tp  &&   ! tp -> next[t] ) tp =  tp -> prefix;
            p
-> next[t] -> prefix =   ! tp ?  root: tp -> next[t];

            
if ( tp  &&  tp -> next[t] -> fail !=   - 1  )
            p
-> next[t] -> fail =  tp -> next[t] -> fail;
            
            q.push( p
-> next[t] );
        }
    }
}

void  ac_run(  char *  s ){
    Trie 
* p =  root,  * q;
    
for int  x =   0 * s; s ++ , x ++  ){
        
int  t =   * s -   ' a ' ;
        
while ! p -> next[t]  &&  p !=  root ) p =  p -> prefix;
        p
=  p -> next[t];
        
if ! p ) p =  root; q =  p;

        
while ( q !=  root  &&  q -> fail !=   - 1   ){
            
if ( q -> idx !=   - 1  ){
                cnt1[q
-> idx] ++ ;
                
if ( x -  q -> level  >  pos[q -> idx] ){
                    pos[q
-> idx] =  x;
                    cnt2[q
-> idx] ++ ; }
            }
            q
=  q -> prefix;
        }
    }
}

int  main(){
    
int  test =   1 ;
    
while ( scanf( " %s " ,str) !=  EOF ){
        scanf(
" %d " , & n );
        init();
        
for int  i =   1 ; i <=  n;  ++ i ){
            scanf(
" %d " , d +  i );
            scanf(
" %s " , s[i] );
            insert( s[i], i );
        }
        prefix();
        ac_run( str );
        
        printf(
" Case %d\n " , test ++  );
        
for int  i =   1 ; i <=  n;  ++ i ){
            
int  t =  search( s[i] );
            
if ( d[i] ==   0  )  printf( " %d\n " , cnt1[t] );
            
else             printf( " %d\n " , cnt2[t] );
        }
        puts(
"" );
    }
    
    
return   0 ;
}





#include  < stdio.h >
#include 
< stdlib.h >
#include 
< string .h >

#define  N 100010

struct  Trie {
    
int  next[ 26 ], fail, idx, h;
    
void  init() {
        
for int  i =   0 ; i <   26 ++ i ) next[i] =   0 ;
        fail
=   - 1 ; idx =   - 1 ; h =   0 ; }

}
tb[N * 6 ];

int  sz =   0 ;

char  str[N];
int   n, data[N], cnt1[N], cnt2[N], pos[N];
char  ss[N][ 7 ];

void  init() {
    sz
=   0 ; tb[ 0 ].init();
    
for int  i =   0 ; i <=  n;  ++ i ) {
        cnt1[i]
=   0 , cnt2[i] =   0 ; pos[i] =   - 1 ; }

}


void  insert(  char *  s,  int  d ) {
    
int  rt =   0 ;
    
for ( ;  * s; s ++  ) {
        
int  t =   * s -   ' a ' ;
        
        
if ( tb[rt].next[t] ==   0  ) {
            sz
++ ; tb[sz].init(); tb[sz].h =  tb[rt].h +   1
            tb[rt].next[t]
=  sz; }

        rt
=  tb[rt].next[t];
    }

    
if ( tb[rt].idx ==   - 1  )  tb[rt].idx =  d; 
}


int  search(  char *  s ) {
    
int  rt =   0 ;
    
for ( ;  * s; s ++  ) {
        
int  t =   * s -   ' a ' ;
        
if ( tb[rt].next[t] ) rt =  tb[rt].next[t];
        
else   return   - 1 ;
    }

    
return  tb[rt].idx;
}


int  que[N * 6 ];

void  prefix() {
    
int  head =   0 , tail =   0 , now, p, f; 
    que[
0 ] =   0 ;
    
while ( head <=  tail ) {
        now
=  que[head ++ ];
        
for int  i =   0 ; i <   26 ++ i )
        
if ( tb[now].next[i] ) {
            p
=  tb[now].next[i]; f =  tb[now].fail;
            
            
while ( f !=   - 1   &&  tb[f].next[i] ==   0  ) f =  tb[f].fail;
            
if ( f ==   - 1  ) tb[p].fail =   0 ;
            
else  tb[p].fail =  tb[f].next[i];
            que[
++ tail] =  p;
        }

    }

}


void  ac_run(  char *  s ) {
    
int  rt =   0 , f, p;
    
    
for int  x =   1 * s; s ++ , x ++  ) {
        
int  t =   * s -   ' a ' ;
            
        
while ( rt >   0   &&  tb[rt].next[t] ==   0  )  rt =  tb[rt].fail;
        
if ( rt !=   - 1  ) rt =  tb[rt].next[t];
        
else  rt =   0 ;
        
        p
=  rt;
        
while ( p >   0  ) {
            
if ( tb[p].idx >   0  ) {
                cnt1[ tb[p].idx ]
++ ;
                
if ( x -  tb[p].h >=  pos[ tb[p].idx ] ) {
                    cnt2[ tb[p].idx ]
++ ;  pos[ tb[p].idx ] =  x; }

            }

            p
=  tb[p].fail;
        }

    }

}


int  main() {
    
int  test =   1 ;
    
while ( scanf( " %s " , str ) !=  EOF ) {
        scanf(
" %d " & n );
        
        init();
        
char  s[ 10 ];
        
for (   int  i =   1 ; i <=  n;  ++ i ) {
            scanf(
" %d %s " , data +  i, ss[i] );
            insert( ss[i], i );
        }

        prefix();
        ac_run( str );
        
        printf(
" Case %d\n " , test ++  );
        
for int  i =   1 ; i <=  n;  ++ i ) {
            
int  t =  search( ss[i] );
            
            
if ( data[i] ==   0  ) printf( " %d\n " , cnt1[t] );
            
else  printf( " %d\n " , cnt2[t] );
        }

        puts(
"" );
    }

    
    
return   0 ;
}

posted on 2009-08-02 22:05 Darren 阅读(779) 评论(1)  编辑 收藏 引用 所属分类: 数据结构

评论:
# re: ZJU 3228 Searching the String ( AC 自动机 ) 2009-08-10 11:09 | 驫犇羴
厉害啊,真的可以用AC自动机计数  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理