本文共 2016 字，大约阅读时间需要 6 分钟。
Oulipo（pku 3461）
法国作家Georges Perec (1936–1982)曾写过一本书《La disparition》，这本书里没有一个字母‘e’。他是Oulipo组织中的一名成员。下面这段话引自这本书：
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…
Perec可能获得很高(或者, 低)的分数在下面这个竞赛中。参赛者被要求写一段关于某个主题的文章，而且文章中出现某个给定单词的次数尽可能少。我们的任务是帮评委写一个程序，用来得到参赛者的排名。参赛者经常写一些字数很长但又毫无意义的文章，如一片文章里连续出现500,000个字母'T'也是很常见的，而且他们从不使用空格。
所以我们想要快速的找出一个单词或是给定的字符串，在一段文章中出现里多少次。给定的单词W和文章T都只包括26个大写英文字母，计算单词W在整篇文章T中出现的次数。W在T中出现的次数必须连续完全匹配，每两次匹配可能有重叠部分。
输入：
输入文件的第一行是一个数字：有多少组测试数据。每组测试数据按一下格式：
第一行是给定的字符串W，只包含大写英文字母，并且1 ≤ |W| ≤ 10,000 ( |W|表示W的长度)。
第二行是文章T，只包含大写英文字母，并且|W| ≤ |T| ≤ 1,000,000。
输出：
对于每组测试数据，输出一行为一个数字，即W在T中出现的次数。
输入样例：
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
输出样例：
1
3
0
分析：
要得到W在T中出现的次数，即看W在T中能匹配成功多少次，这就要用到KMP匹配算法。先求出给定字符串W的next指针，然后进行匹配，当一次匹配成功后继续向后匹配，直至主串T的串尾。此时得到的匹配成功次数为所求，即W在T中出现的次数。
代码：
#include#include #include using namespace std;const int maxn = 1000010;char T[maxn], W[10010];int next[10010]; //记录模式串的next指针void get_next(int len) //获得模式串的next指针{ next[0] = -1; int i = 0, j = -1; while(i < len) { if(j == -1 || W[i] == W[j]) next[++i] = ++j; else j = next[j]; }}int KMP(){ int len1 = strlen(T), len2 = strlen(W); get_next(len2); int i = 0, j = 0; int ans = 0; while(i < len1) { if(j == -1 || T[i] == W[j]) i++, j++; else j = next[j]; if(j == len2) ans++, j = next[j]; } return ans;}int main(){ int n; scanf("%d", &n); while(n--) { scanf("%s", W); scanf("%s", T); int ans = KMP(); printf("%d\n", ans); } return 0;}
转载地址：http://msali.baihongyu.com/