Oulipo-欧力波
HDU - 1686
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.
法国作家乔治·佩雷克 (Georges Perec,1936-1982) 曾写过一本书《消失》,但没有字母“e”。他是Oulipo集团的成员。书中引述:一切看起来都很正常,但一切都声称是错误的。一开始一切正常,然后就出现了不人道的、令人抓狂的。他很想知道将他与小说联系起来的联想是在哪里表达的:在他的地毯上,任何时候都在冲击他的想象力,禁忌的直觉,隐晦的邪恶,空洞的事物的愿景。 :愿景,对控制一切的遗忘的预期,在那里理性被废除:一切看起来都很正常,但......
在接下来的比赛中,佩雷克可能会获得高分(或者更确切地说,低分)。人们被要求就某个主题写一篇甚至可能有意义的文本,尽可能少地出现给定的“单词”。我们的任务是为陪审团提供一个计算这些事件的程序,以获得参赛者的排名。这些竞争者经常写出很长的废话;500,000 个连续的“T”序列并不罕见。他们从不使用空格。
所以我们想快速找出一个词,即给定的字符串,在文本中出现的频率。更正式地:给定字母表 {'A', 'B', 'C', ..., 'Z'} 和该字母表上的两个有限字符串,一个单词 W 和一个文本 T,计算 W 在 T 中的出现次数. W 的所有连续字符必须与 T 的连续字符完全匹配。出现可能重叠。
输入
输入文件的第一行包含一个数字:要遵循的测试用例的数量。每个测试用例具有以下格式:
一行包含单词 W,一个字符串在 {'A', 'B', 'C', ..., 'Z'} 上,其中 1 ≤ |W| ≤ 10,000(此处 |W| 表示字符串 W 的长度)。
一行文本 T,一个字符串在 {'A', 'B', 'C', ..., 'Z'} 上,带有 |W| ≤ |T| ≤ 1,000,000。
输出
对于输入文件中的每个测试用例,输出应该在一行中包含一个数字:单词 W 在文本 T 中出现的次数。
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
题意描述:给你n组数据,每组包含两行字符串,求第一行字符串在第二行出现的次数。
解题思路:根据next数组和kmp字符串匹配求,因为题中要求的是出现的次数,也就是可以重合,即当你利用kmp字符串匹配到给的子串的时候,只需将当时长度字符串位置不变,把子串从头开始和长串匹配。
易错分析:利用输入输出流会超时
AC
#include<stdio.h> #include<string.h> int ne[10010]; char f[1000050],s[10050]; int a,b; void getnext() { int j=0,k=-1; ne[0]=-1; while(j<b) { if(k==-1||s[j]==s[k])//s[k]前缀,s[j]后缀 { j++; k++; // if(s[j]!=s[k]) ne[j]=k; // else // ne[j]=ne[k]; } else { k=ne[k]; } } } int kmp() { int sum=0; int i=0,j=0; getnext(); while(i<a) { if(j==-1||f[i]==s[j]) { i++; j++; if(j==b) { sum++; //i=i-j+2; // j=0;//长的不变,子串从0开始接着找 j=ne[j]; } } else j=ne[j]; } return sum; } int main() { int n,ans; scanf("%d",&n); while(n--) { scanf("%s %s",s,f); memset(ne,0,sizeof(ne)); a=strlen(f); b=strlen(s); ans=kmp(); printf("%d\n",ans); } return 0; }