这道题想了好久,,提交了好久,,改了好久,,,,,终于ac了,,,,,,学KMP的伤不起啊!!!!!前几天做了不可重复利用的子串的个数,,当时是1A了,本以为这题应该也不难,,,却悲剧了这么久。。。。现在已经不是一天做几道题,,而是几天做一道题,,,,题目:
Oulipo
Time Limit:1000MS |
|
Memory Limit:65536K |
Total Submissions:9360 |
|
Accepted:3708 |
Description
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter'e'. He was a member of the Oulipo group. A quote from the book:
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 would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program
that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive'T's is not unusual. And they never use spaces.
So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A','B','C', …,'Z'} and two finite strings over that alphabet, a wordWand a textT,
count the number of occurrences ofWinT. All the consecutive characters of W must exactly match consecutive characters ofT. Occurrences may overlap.
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 wordW, a string over {'A','B','C', …,'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the stringW).
- One line with the textT, 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 wordWin the textT.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
ac代码:
分享到:
相关推荐
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj 2744子串 答案 所用的是最简单的C语言
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
供初学编程基本算法的人练习使用,在poj.grids.cn上
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ各题算法分类和题目推荐.pdf
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
关于C++ 算法 北大网站POJ 八数码问题
北大POJ中级-基本算法 解题报告+AC代码
用贪心算法解决POJ 1065的木棍处理问题
poj1113 melkman算法求凸包, 使用STL
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类