问题1410--Oulipo

1410: Oulipo

时间限制: 1 Sec  内存限制: 128 MB
提交: 167  解决: 74
[状态] [讨论版] [提交] [命题人:]
题目描述
       法语作家Georges Perec (1936–1982) 曾经写过一本没有字母e的书La disparition,他是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的序列是常见的;而且他们从来不使用空格。
因此,给出一个字符串,我们要很快地发现这个字符串在一段文本中出现的次数。更规范的讲,给出字母表{'A', 'B', 'C', …, 'Z'}以及字母表上的两个有限的字符串:一个单词W和一段文本T,计算WT中出现的次数。所有W的连续字符必须严格地匹配T的连续字符。在文本T中,单词W的出现可能会重叠在一起。
输入
输入文件的第一行给出一个整数,代表后面给出的测试用例的个数。每个测试用例的格式如下:
一行给出单词W,一个在字母表{'A', 'B', 'C', …, 'Z'}上的字符串,1 ≤ |W| ≤ 10,000|W|表示字符串W的长度)。
一行给出文本T,一个在字母表{'A', 'B', 'C', …, 'Z'}上的字符串,|W| ≤ |T| ≤ 1,000,000。
输出
对于输入文件中的每个测试用例,在一行中输出一个数字:单词W在文本T中出现的次数。
样例输入 Copy
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
样例输出 Copy
1
3
0
来源/分类