hdu----1686 Oulipo (ac自动机)
Oulipo
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6227 Accepted Submission(s): 2513
Problem Description
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book: Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais… Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces. So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.
Input
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format: One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W). One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.
Output
For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
Source
ac自动机做法：
代码：
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<iostream>
5 #include<queue>
6
7 using namespace std;
8 const int maxn=26;
9
10 struct node{
11
12 node *child[maxn];
13 node * fail ; //失败指针
14 int tail ;
15
16 };
17 void init(node * tmp){
18 for(int i=0;i<maxn;i++)
19 tmp->child[i]=NULL;
20 tmp->fail=NULL;
21 tmp->tail=0;
22 }
23
24
25 //建立一颗字典树
26
27 void Buildtree(const char ss [] ,node * root){
28 node *cur;
29 for(int i=0; ss[i] ; i++){
30 int no =ss[i]-'A';
31 if(root->child[no]==NULL){
32 cur = new node ;
33 init(cur);
34 root->child[no]=cur;
35 }
36 root = root->child[no];
37 }
38 root->tail++;
39 }
40
41 //构造失败指针
42 void BuildFail(node * root){
43
44 queue<node *> tmp;
45 tmp.push(root);
46 node *cur,*po;
47 while(!tmp.empty()){
48 cur = tmp.front();
49 tmp.pop(); //出队列
50 for(int i=0 ; i<maxn ; i++){
51 if( cur->child[i] != NULL ){
52 if(cur==root){
53 cur->child[i]->fail=root; //指向树根
54 }else{
55 po = cur ;
56 while(po->fail){
57 if(po->fail->child[i]){
58 cur->child[i]->fail=po->fail->child[i];
59 break;
60 }
61 po = po->fail;
62 }
63 if(po->fail==NULL)
64 cur->child[i]->fail=root;
65 }
66 tmp.push(cur->child[i]);
67 }
68 }
69 }
70 }
71
72 //查询
73 int Query(char ss [] , node *root){
74
75 node *cur , *tmp;
76 cur =root;
77 int pos=-1,res=0;
78
79 for(int i=0; ss[i] ;i++){
80
81 pos= ss[i]-'A';
82 while(cur->child[pos]==NULL&&cur!=root)
83 cur = cur->fail;
84 cur = cur->child[pos];
85 if(cur==NULL) cur=root;
86 tmp = cur;
87 while(tmp!=root&&tmp->tail>0){
88 res+=tmp->tail;
89 tmp = tmp->fail;
90 }
91 }
92
93 return res;
94
95 }
96 char sa[10010],sb[1000010];
97 int main(){
98 int te;
99 node *root;
100 scanf("%d",&te);
101 while(te--){
102 root = new node ;
103 init(root);
104 scanf("%s %s",sa,sb);
105 Buildtree(sa,root);
106 BuildFail(root);
107 int ans =Query(sb,root);
108 printf("%d\n",ans);
109 }
110 return 0;
111 }