oulipo——KMP
传送门
法国作家乔治·佩雷克（Georges Perec，1936-1982）曾经写过一本书，没有字母“e”。他是Oulipo小组的成员。书中的一句话：
一切都有正常的对等，但一切都声称是假的。一切都正常，首先，非人出现了，吓坏了他。他很想知道将他与小说联系在一起的关联在哪里：搅动他的地毯，随时攻击他的想象力，禁忌的直觉，晦涩邪恶的景象，空洞的东西，不言而喻的：异象，遗忘的异象支配一切，理性被废除：一切看起来正常，但......
佩雷克可能会在随后的比赛中得分很高（或者更确切地说，得分很低）。人们被要求在某个主题上写一篇甚至可能有意义的文本，尽可能少地出现一个给定的“单词”。我们的任务是为陪审团提供一个计算这些事件的程序，以获得竞争对手的排名。这些竞争对手经常写很长的文字，毫无意义;连续500，000个序列的“T”并不罕见。他们从不使用空间。
因此，我们希望快速找出单词（即给定字符串）在文本中出现的频率。更正式地说：给定字母表{'A'，'B'，'C'，...，'Z'}和该字母表上的两个有限字符串，一个单词W和一个文本T，计算W在T中的出现次数。W 的所有连续字符必须与 T 的连续字符完全匹配。具体值可能会重叠。
Input
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
- One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
- One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.
Output
For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.
Sample
| Inputcopy | Outputcopy |
|---|---|
3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN | 1 3 0 |
#include
#include
#include
#include
using namespace std;
void get_next(char ch[],int l,int next[])//数组从0开始计数
{next[0]=-1;int i=0,j=-1;while(i<=l){if(j==-1||ch[i]==ch[j])next[++i]=++j;elsej=next[j];}
}int num(int ll,int l,int next[],char a[],char b[])
{int j=0,ans=0;for(int i=0;i0){j=next[j];}if(b[i]==a[j]){j++;}if(j==l){ans++;j=next[j];}}return ans;
}int main()
{int n;cin>>n;char a[10005];char b[1000005];int l,ll,next[10005];while(n--){cin>>a>>b;l=strlen(a);ll=strlen(b);get_next(a,l,next);cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！