hdu2896AC自动机

ac自动机题目 &＃xff0c; 和hdu2222差不多&＃xff0c;不过这里的字符包含ASCII所有可见字符&＃xff0c;所以在建立trie树是需要将数组开大&＃xff0c;否则就会访问越界&＃xff0c;又是纠结好久&＃xff0c;又看了一遍题目才发现。

#include
#include
#include
#include
#include using namespace std;#define MAXN 100
#define MAXX 100100
int sum ;
char arr[MAXX];
int flag[505];struct node
{int num;char str;node *fail;node *next[MAXN];node(){num &＃61; 0;fail &＃61; NULL;for(int i &＃61; 0 ; i };void Insert(node *root,char a[], int k)
{node *current , *newnode;int len &＃61; strlen(a);current &＃61; root ;for(int i &＃61; 0 ; i next[m] !&＃61; NULL){current &＃61; current -> next[m];if(i &＃61;&＃61; len - 1) (current -> num) &＃61; k ;}else{newnode &＃61; new node();newnode -> str &＃61; a[i];current -> next[m] &＃61; newnode;current &＃61; newnode;if(i &＃61;&＃61; len - 1) (current -> num) &＃61; k;}}
}void BuildFail(node *root)
{queue Q;root -> fail &＃61; root;for(int i &＃61; 0 ; i next[i] &＃61;&＃61; NULL){root -> next[i] &＃61; root ;}else{root -> next[i] -> fail &＃61; root ;Q.push(root -> next[i]);}}while(!Q.empty()){node *current ;current &＃61; Q.front();Q.pop();for(int i &＃61; 0 ; i next[i] &＃61;&＃61; NULL)current -> next[i] &＃61; current -> fail -> next[i];else{// cout < next[i] ->str < next[i] -> fail &＃61; current -> fail -> next[i];Q.push(current -> next[i]);}}}
}void Query(node *root,char a[])
{node *current , *newnode;int len &＃61; strlen(a);current &＃61; root;for(int i &＃61; 0 ; i next[m] &＃61;&＃61; NULL && current !&＃61; root) current &＃61; current -> fail;current &＃61; current -> next[m];newnode &＃61; current ;while(newnode !&＃61; root){if(1 <&＃61; newnode -> num&& newnode -> num <505) flag[newnode -> num] &＃61; 1 ;newnode &＃61; newnode -> fail ;}}
}int main()
{int n;while( scanf("%d" , &n) !&＃61; EOF){node *root &＃61; new node();getchar();char a[205];for(int i &＃61; 0 ; i }