HZNUOJ

KMP的内存优势

Tags:
Time Limit:  10 s      Memory Limit:   5 MB
Submission:115     AC:10     Score:99.52

Description

请尽量用C/C++语言完成本题,因为其他语言有内存补贴,可能会卡不住内存(事实上好像卡住了)。

使用KMP算法完成本题。

输入两个字符串t,s,找出t在s中第一次出现的位置。

题目保证t在s中出现过,且|t|<|s|。

注意内存限制。

Input

两行,两个字符串t,s

|t|<=10

|s|<=5*10^7

Output

一个整数,表示第一次出现的位置,从0开始计数。

Samples

input
a ssa
output
2

Hint

辣鸡题目我偏不用KMP做。

sunday算法:将模式串和母串对齐,当发现的匹配失败时候就判断模式串的后一位在母串的字符是否在模式串中存在?如果存在则将该位置和模式串中的该字符对齐,再从头开始匹配。如果不存在就将模式串向后移动,和母串k+1处的字符对齐,再进行匹配。重复上面的操作直到找到,或母串被找完结束。 

直接存下来会爆内存 用一个比模式串长度大一的字符串不停覆盖把母串分段存下来。

——HU, Jiacheng

标准KMP解法:

利用KMP算法i指针不回溯的特性,一边读入一边查找即可。

——Wei, Lixin

Author

WEI, Lixin