HDU2896+AC自动机-白红宇

HDU2896+AC自动机

阅读量：5034 次

发布时间：2019-06-12

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

ac自动机模板题

1 /*  2   3 */  4 #include
      
         5 #include
       
          6 #include
        
           7 #include
         
            8 #include
          
             9 #include
           
             10 #include
             11 #include
             
               12 #include
              
                13 #include
               
                 14 using namespace std; 15 typedef long long int64; 16 //typedef __int64 int64; 17 typedef pair
                
                  PII; 18 #define MP(a,b) make_pair((a),(b)) 19 const int maxn = 100; 20 const int maxm = 10005; 21 const int inf = 0x7fffffff; 22 const double pi=acos(-1.0); 23 const double eps = 1e-8; 24 25 struct Tree{ 26 int id; 27 Tree *fail; 28 Tree *next[ maxn ]; 29 }; 30 Tree root; 31 Tree *q[ 20000005 ]; 32 char str[ maxm ]; 33 int tot; 34 int cnt[ 555 ]; 35 int Index_cnt ; 36 bool vis[ 555 ]; 37 38 void init(){ 39 root.id = 0; 40 root.fail = NULL; 41 for( int i=0;i
                 
                  next[ id ]==NULL ){ 52 tmp = (Tree *)malloc(sizeof( root )); 53 tmp->id = 0; 54 for( int j=0;j
                  
                   next[ j ] = NULL; 56 p->next[ id ] = tmp; 57 p = p->next[ id ]; 58 } 59 else 60 p = p->next[ id ]; 61 } 62 p->id = ID; 63 return ; 64 } 65 66 void build_AC(){ 67 int head = 0,tail = 0; 68 Tree *p = &root; 69 Tree *tmp = NULL; 70 q[ tail++ ] = p; 71 while( head!=tail ){ 72 p = q[ head++ ]; 73 for( int i=0;i
                   
                    next[i]!=NULL ){ 75 if( p==(&root) ){ 76 p->next[i]->fail = &root; 77 } 78 else{ 79 tmp = p->fail; 80 while( tmp!=NULL ){ 81 if( tmp->next[i]!=NULL ){ 82 p->next[i]->fail = tmp->next[i]; 83 break; 84 } 85 tmp = tmp->fail; 86 } 87 if( tmp==NULL ) 88 p->next[i]->fail = &root; 89 } 90 q[ tail++ ] = p->next[i]; 91 } 92 } 93 } 94 } 95 96 void query( char str[] ){ 97 int len = strlen( str ); 98 Tree *p = &root; 99 Tree *tmp = NULL;100 for( int i=0;i
                    
                     next[id]==NULL&&p!=(&root) ){103 p = p->fail;104 }105 p = p->next[ id ];106 if( p==NULL )107 p = &root;108 tmp = p;109 while( tmp!=(&root) ){110 if( tmp->id!=0&&vis[tmp->id]==false ){111 vis[tmp->id] = true;112 cnt[ Index_cnt++ ] = tmp->id;113 }114 tmp = tmp->fail;115 }116 }117 return ;118 }119 120 int main(){121 int n,m;122 while( scanf("%d",&n)!=EOF ){123 init();124 char s[ 255 ];125 for( int i=1;i<=n;i++ ){126 scanf("%s",s);127 build( s,i );128 }129 build_AC();130 scanf("%d",&m);131 tot = 0;132 for( int i=1;i<=m;i++ ){133 scanf("%s",str);134 Index_cnt = 0;135 memset( vis,false,sizeof( vis ) );136 query( str );137 if( Index_cnt!=0 ) {138 tot++;sort( cnt,cnt+Index_cnt );139 printf("web %d:",i);140 for( int j=0;j