# 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 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

### hdu 1829 A Bug's Life（分组并查集（偏移量））

A Bug's Life Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/3276...

37780

30360

### HDUOJ---------(1045)Fire Net

Fire Net Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (...

34350

### 《eloquent javascript》 notes1

There is only one value in JavaScript that is not equal to itself, and that is N...

9730

### 3893: [Usaco2014 Dec]Cow Jog

3893: [Usaco2014 Dec]Cow Jog Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 17...

30450

37060

### 3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

33880

### HDUOJ----(4788)Hard Disk Drive

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Ot...

35690

### Hibernate 中集合对象的抓取策略(Fetching strategies)

/**  * Product entity. @author MyEclipse Persistence Tools  */

7010

### 1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

35070