来自我的个人网站。 http://www.heroscar.com
Oulipo
Time Limit:1000MS |
|
Memory Limit:65536K |
Total Submissions:12706 |
|
Accepted:5075 |
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
题目大意: 赤裸裸的KMP。就是求 子串 在 主串中出现的次数。
题目思路: KMP 。KMP 重要的就是 next数组的建立。next数组就是对 子串 在与 主串匹配时加了预处理。
使得匹配效率提升了很多。避免了不必要的匹配。预处理也就是求next数组这里可能难理解一点
http://baike.baidu.com/view/574553.htm
#include;
#include;
int next[10050];
char p[10050],t[1001000];
void get_next(char *a,int len);
int main()
{
// freopen("in.txt","r",stdin);
int n,lenp,lent,i,j;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
int sum=0;
i=0,j=0;
scanf("%s%s",p,t);
lenp=strlen(p);
lent=strlen(t);
get_next(p,lenp); //求next数组
// for(i=0;i<lenp;i++)
// printf("%d ",next[i]);
while(i<lent) //匹配
{
if(j==-1|| t[i]==p[j])
{
i++; j++;
if(j==lenp)
{
sum++;
j=next[j];
}
}
else j=next[j];
}
printf("%d\n",sum);
}
}
return 0;
}
void get_next(char *a,int len)
{
int i=0,j=-1;
next[0]=-1;
while(i<len) //很巧妙的方法。
{
if(j==-1 || a[i]==a[j])
{
i++; j++;
next[i]=j;
}
else j=next[j];
}
}
分享到:
相关推荐
POJ3211--Washing Clothes
POJ水题集-----50道左右-----增加自信啊..
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ初级题-数据结构:解题报告+AC代码
POJ3259--Wormholes,使用bellman方法。
poj题目分类--acmer做题极有用资源
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
北大POJ3414-Pots 解题报告+AC代码
poj 2827 Auto-Calculation Machine.md
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
用Java代码实现POJ(PKU)上题2494!
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
1390--blocks.rar
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助