问题1410--Oulipo

1410: Oulipo

时间限制: 1Sec 内存限制:128 MB
提交:193 解决:83
[ 状态] [ 讨论版] [ 提交] [命题人: ]
题目描述
法语作家 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 ,计算 W T 中出现的次数。所有 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
来源/分类