HDU-1686 Oulipo

学习：重点理解这句话的意思： next[j]会告诉我们从哪里开始匹配模板题。

Oulipo

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3612 Accepted Submission(s): 1428

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

华东区大学生程序设计邀请赛_热身赛

Recommend

lcy

 1 #include"stdio.h"
 2 #include"string.h"
 3 int next[10001],num;
 4 char a[1000001],b[10001];
 5 int lena,lenb;
 6 void  get_next()
 7 {
 8  int i,j;
 9  i=0;next[0]=-1;j=-1;
10  while(i<lenb)
11  {
12   if(j==-1||b[i]==b[j])
13   {
14    i++;
15    j++;
16    if(b[i]==b[j])
17    {
18     next[i]=next[j];
19    }
20    else
21    {
22     next[i]=j;
23    }
24   }
25   else
26   {
27    j=next[j];
28   }
29  }
30 }
31 void kmp()
32 {
33  int i,j;
34   i=0;
35   j=0;
36   num=0;
37  while(i<lena)
38  {
39   if(a[i]==b[j]||j==-1)
40   {
41    i++;
42    j++;
43   }
44   else
45   {
46    j=next[j];
47   }
48   if(j==lenb)//当j==Lenb next[j]会告诉我们从哪里开始匹配
49   {
50      num++;
51      j=next[j];
52   }
53  }
54  printf("%d
",num);
55 }
56 int main()
57 {
58  int n;
59  while(scanf("%d",&n)!=EOF)
60  {
61        getchar();
62   while(n--)
63   {
64      gets(b);
65      gets(a);
66      lena=strlen(a);
67      lenb=strlen(b);
68       get_next();
69      kmp();
70   }
71  }
72  return 0;
73 }

HDU-1686 Oulipo

学习：重点理解这句话的意思： next[j]会告诉我们从哪里开始匹配 模板题。

Oulipo

学习：重点理解这句话的意思： next[j]会告诉我们从哪里开始匹配模板题。