【题目描述】
法国作家乔治·佩雷克(Georges Perec,1936-1982)曾经写过一本书,《敏感字母》(La disparition),全篇没有一个字母‘e’。他是乌力波小组(Oulipo Group)的一员。下面是他书中的一段话:
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…
佩雷克很可能在下面的比赛中得到高分(当然,也有可能是低分)。在这个比赛中,人们被要求针对一个主题写出甚至是意味深长的文章,并且让一个给定的“单词”出现次数尽量少。我们的任务是给评委会编写一个程序来数单词出现了几次,用以得出参赛者最终的排名。参赛者经常会写一长串废话,例如500000个连续的‘T’。并且他们不用空格。 因此我们想要尽快找到一个单词出现的频数,即一个给定的字符串在文章中出现了几次。更加正式地,给出字母表{‘A’,’B’,’C’,…,’Z’}和两个仅有字母表中字母组成的有限字符串:单词W和文章T,找到W在T中出现的次数。这里“出现”意味着W中所有的连续字符都必须对应T中的连续字符。T中出现的两个W可能会部分重叠。
【输入格式】
输入包含多组数据。 输入文件的第一行有一个整数,代表数据组数。接下来是这些数据,以如下格式给出: 第一行是单词W,一个由{‘A’,’B’,’C’,…,’Z’}中字母组成的字符串,保证1<=|W|<=10000(|W|代表字符串W的长度) 第二行是文章T,一个由{‘A’,’B’,’C’,…,’Z’}中字母组成的字符串,保证|W|<=|T|<=1000000。
【输出格式】
对每组数据输出一行一个整数,即W在T中出现的次数。
【样例输入】
3BAPCBAPCAZAAZAZAZAVERDIAVERDXIVYERDIAN
【样例输出】
130
题解
就是MP板子
/* * @Author: WildRage * @Date: 2017-06-12 17:26:02 * @Last Modified by: WildRage * @Last Modified time: 2017-06-12 19:01:45 */#include<cstdio>#include<cstring>using namespace std;char S[1000005],T[1000005];int next[1000005];int len;void get_next(char *a,int n){ int j=0,k=-1; next[0]=-1; while(j<n){ if(k==-1||T[j]==T[k]){ next[++j]=++k; } else k=next[k]; }}int main(){ freopen("oulipo.in","r",stdin); freopen("oulipo.out","w",stdout); int t; scanf("%d",&t); while(t--){ int ans=0; scanf("%s",T);scanf("%s",S); int n=strlen(S); int m=strlen(T); get_next(T,m); int i=0,j=0; for(int i=0;i<n;i++){ while(j>0&&S[i]!=T[j]) j=next[j]; if(S[i]==T[j])j++; if(j==m)ans++,j=next[j]; } printf("%d\n",ans); }}