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中出現的次數。

【樣例輸入】

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

【樣例輸出】

【來源】

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 }

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。