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

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #pragma warning ( disable : 4996 )  7 using namespace std;  8   9 inline int Max(int a,int b) { return a>b?a:b; } 10 inline int Min(int a,int b) { return a>b?b:a; } 11 const int inf = 0x3f3f3f3f; 12 const int maxn = 1e6+5; 13 const int maxk = 100; 14  15 int N, M, tot; 16 int ans[5]; 17 char str[205], test[10005]; 18  19 struct node { 20     node* next[maxk]; 21     node* fail; 22     int code; 23     bool end; 24     node() { 25         memset( next, NULL, sizeof(next) ); 26         fail = NULL; 27         code = 0; end = false; 28     } 29 }; 30  31 void insert( node* root, int x ) 32 { 33     node* p = root; 34     int len = strlen(str); 35     int tmp; 36  37     for ( int i = 0; i < len; i++ ) 38     { 39         tmp = str[i]-32; 40         if ( p->next[tmp] == NULL ) 41             p->next[tmp] = new node(); 42         p = p->next[tmp]; 43         p->code = x; 44     } 45     p->end = true; 46 } 47  48 void getnotfail( node* root ) 49 { 50     queue
           
             q; 51 root->fail = NULL; 52 q.push(root); 53 while (!q.empty()) 54 { 55 node *run= q.front(); q.pop(); 56 node *tmp = NULL; 57 for ( int i = 0; i < maxk; i++ ) 58 { 59 if ( run->next[i] ) 60 { //如果节点是初始节点，则它的子节点的失败指针全部指向root 61 if(run==root) run->next[i]->fail = root; 62 else 63 { 64 tmp = run->fail; //tmp为它的父节点的上层节点 65 while (tmp) 66 { 67 if(tmp->next[i]) //寻找tmp的第i个子节点,如果存在，则run的fail指针指向它 68 { run->next[i]->fail = tmp->next[i]; break; } 69 tmp = tmp->fail; 70 } 71 if(tmp==NULL) 72 run->next[i]->fail = root; 73 } 74 q.push(run->next[i]); 75 } 76 } 77 } 78 } 79 80 int query( node* r ) 81 { 82 int cnt = 0; 83 int len = strlen(test); 84 node* p = r; 85 for ( int i = 0; i < len; i++ ) 86 { 87 int x = test[i]-32; 88 while (!p->next[x]&&p!=r) p = p->fail; 89 90 p = p->next[x]; 91 if (!p) p = r; 92 node *tmp = p; 93 94 while (tmp!=r&&tmp->end) 95 { 96 ans[cnt++] = tmp->code; 97 tmp = tmp->fail; 98 } 99 }100 return cnt;101 }102 103 int main()104 {105 106 while ( ~scanf("%d", &N ))107 {108 node* r = new node;109 110 for ( int i = 1; i <= N; i++ )111 { scanf("%s", str); insert(r, i); }112 getnotfail(r);113 cin >> M;114 115 116 for ( int i = 1; i <= M; i++ )117 {118 scanf( "%s", test );119 int num = query(r);120 if (num)121 {122 sort(ans, ans + num);123 printf( "web %d:", i );124 for ( int j = 0; j < num; j++ )125 printf(" %d", ans[j]);126 cout << endl;127 tot++;128 memset( ans, 0, sizeof(ans) );129 }130 }131 printf("total: %d\n", tot);132 }133 return 0;134 }