1570. [POJ3461]乌力波

★☆   输入文件:oulipo.in   输出文件:oulipo.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

法国作家乔治·佩雷克(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中出现的次数。

【样例输入】

3

BAPC

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

【样例输出】

1

3

0

 
 #include<iostream>       //KMP
#include<cstring>
#include<cstdio> #define W 10000+10
#define T 1000000+10 using namespace std; char w[W],t[T];
int n,fail[W];
int l1,l2;
int sum=; void Fail();
void doit(); int main()
{
freopen("oulipo.in","r",stdin);
freopen("oulipo.out","w",stdout);
scanf("%d",&n);
while(n--)
{
memset(w,,sizeof(w));
memset(t,,sizeof(t));
memset(fail,,sizeof(fail));
sum=;
scanf("%s%s",w,t);
Fail();doit();
printf("%d\n",sum);
}
fclose(stdin);fclose(stdout);
return ;
}
void Fail() //建立fail数组
{
fail[]=;
l1=strlen(w);
l2=strlen(t);
for(int j=,i=;i<l1;i++)
{
while(j&&w[j]!=w[i]) j=fail[j-];
if(w[j]==w[i]) j++;
fail[i]=j;
}
}
void doit() //搜查单词出现次数
{
int j=;
for(int i=;i<l2;++i)
{
while(j&&w[j]!=t[i])
j=fail[j-];
if(w[j]==t[i]) j++;
if(j==l1)
{
sum++;
j=fail[j-];
}
}
}
05-08 15:34