1570. [POJ3461]乌力波

2018-06-17 22:03:20来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

★☆   输入文件: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

【来源】

BAPC 2006 Qualification

POJ 3461

 

 

KMP的裸题,

但是可以用字符串hash搞,

对于单词a,文章b

我们先求出单词a的hash值,再求出文章b的每一位的hash值,

然后枚举文章b的每一位,判断一下区间是否合法就好

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<map>
 8 #define lli long long int 
 9 #define ull unsigned long long 
10 using namespace std;
11 const ull MAXN=1000001;
12 ull base=27;
13 void read(ull &n)
14 {
15     char c='+';ull x=0;bool flag=0;
16     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
17     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
18     n=flag==1?-x:x;
19 }
20 ull Pow[MAXN];
21 ull ha[MAXN];
22 ull pd(ull l,ull r){return (ull)ha[r]-Pow[r-l+1]*ha[l-1];}
23 char a[MAXN];
24 char b[MAXN];
25 int main()
26 {
27     freopen("oulipo.in","r",stdin);
28     freopen("oulipo.out","w",stdout);
29     ull n;read(n);
30     Pow[0]=1;
31     for(ull i=1;i<=MAXN;i++)
32         Pow[i]=Pow[i-1]*base;
33     while(n--)
34     {
35         int ans=0;
36         scanf("%s%s",a+1,b+1);
37         int la=strlen(a+1);ull lb=strlen(b+1);
38         ull hasha=0;
39         for(ull i=1;i<=la;i++)
40             hasha=hasha*base+a[i];
41         for(ull i=1;i<=lb;i++)
42             ha[i]=ha[i-1]*base+b[i];
43         for(ull i=1;i<=lb-la+1;i++)
44         {
45             ull k=pd(i,i+la-1);
46             if(k==hasha)
47                 ans++;
48         }
49             
50         printf("%d\n",ans);
51     }
52     return 0;
53 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1429 平面最近点对(加强版)

下一篇:LOJ #109. 并查集