HDU2896 病毒侵袭 AC自动机模板

各种MLE，这模板感觉有问题，next数组开128也会MLE，实际上可见字符为编号32~126，只用开100就行。

 #include <iostream>

 #include <cstdio>

 #include <string.h>

 #include <algorithm>

 #include <queue>

 #pragma warning ( disable : 4996 )

 using namespace std;

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 const int inf = 0x3f3f3f3f;

 const int maxn = 1e6+;

 const int maxk = ;

 int N, M, tot;

 int ans[];

 char str[], test[];

 struct node {

     node* next[maxk];

     node* fail;

     int code;

     bool end;

     node() {

         memset( next, NULL, sizeof(next) );

         fail = NULL;

         code = ; end = false;

     }

 };

 void insert( node* root, int x )

 {

     node* p = root;

     int len = strlen(str);

     int tmp;

     for ( int i = ; i < len; i++ )

     {

         tmp = str[i]-;

         if ( p->next[tmp] == NULL )

             p->next[tmp] = new node();

         p = p->next[tmp];

         p->code = x;

     }

     p->end = true;

 }

 void getnotfail( node* root )

 {

     queue<node*> q;

     root->fail = NULL;

     q.push(root);

     while (!q.empty())

     {

         node *run= q.front(); q.pop();

         node *tmp = NULL;

         for ( int i = ; i < maxk; i++ )

         {

             if ( run->next[i] )

             {    //如果节点是初始节点，则它的子节点的失败指针全部指向root

                 if(run==root) run->next[i]->fail = root;

                 else

                 {

                     tmp = run->fail;        //tmp为它的父节点的上层节点

                     while (tmp)

                     {

                         if(tmp->next[i])    //寻找tmp的第i个子节点,如果存在，则run的fail指针指向它

                         { run->next[i]->fail = tmp->next[i]; break; }

                         tmp = tmp->fail;

                     }

                     if(tmp==NULL)

                         run->next[i]->fail = root;

                 }

                 q.push(run->next[i]);

             }

         }

     }

 }

 int query( node* r )

 {

     int cnt = ;

     int len = strlen(test);

     node* p = r;

     for ( int i = ; i < len; i++ )

     {

         int x = test[i]-;

         while (!p->next[x]&&p!=r) p = p->fail;

         p = p->next[x];

         if (!p) p = r;

         node *tmp = p;

         while (tmp!=r&&tmp->end)

         {

             ans[cnt++] = tmp->code;

             tmp = tmp->fail;

         }

     }

     return cnt;

 }

 int main()

 {

     while ( ~scanf("%d", &N ))

     {

         node* r = new node;

         for ( int i = ; i <= N; i++ )

         { scanf("%s", str); insert(r, i); }

         getnotfail(r);

         cin >> M;

         for ( int i = ; i <= M; i++ )

         {

             scanf( "%s", test );

             int num = query(r);

             if (num)

             {

                 sort(ans, ans + num);

                 printf( "web %d:", i );

                 for ( int j = ; j < num; j++ )

                     printf(" %d", ans[j]);

                 cout << endl;

                 tot++;

                 memset( ans, , sizeof(ans) );

             }

         }

         printf("total: %d\n", tot);

     }

     return ;

 }