HDU 2222 Keywords Search AC自动机 可做模板

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;#define NUM 26
#define ST  'a'
#define QMAX 500001
struct Node
{Node *fail;Node *nxt[NUM];int count; // 单词结束点+1Node(){fail = NULL;memset( nxt,0,sizeof(nxt) );count = 0;}
}*Q[QMAX];int head, tail;
char text[5000001]; //文本
void insert( char *str, Node *root )
{int len = strlen( str );Node *temp = root;for( int i = 0;i < len;i++ ){int nxtp = str[i] - ST;if( !temp->nxt[ nxtp ] ){temp->nxt[ nxtp ] = new Node();}temp = temp->nxt[ nxtp ];}temp->count++;
}void Build_AC( Node *root )
{root->fail = NULL;Q[ head++ ] = root;if( head == QMAX ) head = 0;while( head != tail ){Node *temp = Q[tail++];if( tail == QMAX ) tail = 0;Node *p = NULL;for( int i = 0;i < NUM;i++ ){if( temp->nxt[i] ){if( temp == root ) temp->nxt[i]->fail = root;else{p = temp->fail;while( p ){if( p->nxt[i] ){temp->nxt[i]->fail = p->nxt[i];break;}p = p->fail;}if( !p ) temp->nxt[i]->fail = root;}Q[head++] = temp->nxt[i];if( head == QMAX ) head = 0;}}}
}int query( Node *root )
{int result = 0, len = strlen( text );Node *p = root;for( int i = 0;i < len;i++ ){int nxtp = text[i] - ST;while( !p->nxt[nxtp] && p != root ) p = p->fail;p = p->nxt[nxtp];if( !p ) p = root;Node *temp = p;while( temp != root && temp->count != 0 ){result += temp->count;temp->count = 0;temp = temp->fail;}}return result;
}
void Release( Node *root )
{for( int i = 0;i < NUM;i++ ){if( root->nxt[i] ) Release( root->nxt[i] );}delete root;
}int t, n;
Node *root = NULL;
char str[51];int main()
{scanf( "%d",&t );while( t-- ){head = tail = 0;root = new Node();scanf( "%d",&n );while( n-- ){scanf( "%s",str );insert( str,root );}Build_AC( root );scanf( "%s",text );printf( "%d\n", query( root ) );//Release( root );  //销空间能免就省吧}
}