KMP --關于cogs1570 烏力波-有解無憂

題目鏈接：http://cogs.pro:8081/cogs/problem/problem.php?pid=vQzXJkgWa

【題目描述】

法國作家喬治·佩雷克(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

【樣例輸出】

思路：這是一道裸的KMP演算法題，題目中模式串在第一行，主串在第二行，按順序讀入即可，如果用string存，可能會超時，因此用char陣列存盤，但是在存盤時不要用char[0]來表示字串長度，此時資料型別為char，范圍最多只有0-255，因此要額外設int型變數來存字串長度，用《資料結構 C語言版》清華出版的那本書上的KMP模板會超時，可能是因為 j 多余了，每次都先找到相匹配的位置，j 達到模式串長度時ans+1即可，

代碼：

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include <iostream>
 3 #include <cstdio>
 4 #define MAXLENGTH 10000
 5 using namespace std;
 6 //typedef unsigned char SString[1000100];
 7 int nextP[1000100];
 8 char s[1000100], t[1000100];
 9 int slen, tlen;
10  
11 void getNext(char*);
12 int indexKMP(char*, char*, int);
13 int getLen(char*);
14  
15 void getNext(char* T)
16 {
17     int i = 0, j = -1;
18     nextP[0] = -1;
19     while (i < tlen)
20     {
21         if (j == -1 || T[i] == T[j])
22         {
23             ++i, ++j;
24             if (T[i] != T[j])
25                 nextP[i] = j;
26             else
27                 nextP[i] = nextP[j];
28         }
29         else
30             j = nextP[j];
31     }
32 }
33  
34 int indexKMP(char* S, char* T, int pos) //從pos處開始匹配
35 {
36     int i = pos, j = 0, res = 0;
37     getNext(T);
38     while (i < slen)
39     {
40         while (j != -1 && S[i] != T[j]) j = nextP[j];
41         i++, j++;
42         if (j == tlen)
43             res++;
44     }
45     return res;
46 }
47  
48 int getLen(char* T)
49 {
50     int len = 0;
51     for (int i = 0; T[i] != '\0'; i++)
52         len++;
53     return len;
54 }
55 int main()
56 {
57     freopen("oulipo.in", "r", stdin);
58     freopen("oulipo.out", "w", stdout);
59     int x;
60     cin >> x;
61     while (x--)
62     {
63         scanf("%s%s", t, s);
64         slen = getLen(s);
65         tlen = getLen(t);
66         cout << indexKMP(s, t, 0) << endl;
67     }
68     return 0;
69 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138112.html

標籤：其他

上一篇：順序堆疊實作數制的轉換

下一篇：演算法題--整數轉羅馬數字