Problem 1751 --算法4-6:KMP字符串模式匹配算法实现

1751: 算法4-6:KMP字符串模式匹配算法实现

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 221  Solved: 111
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法,同时前面的例子中也描述了子串移动位置的数组实现的算法。前面你已经实现了子串移动的数组,现在就来利用该数组来实现KMP模式匹配。

下面是相应的算法:

图:KMP算法

Input

3组字符串,每组字符串占一行。每行包含由空格分隔的两个字符串,字符串仅由英文小写字母组成且长度不大于100

Output

每组数据输出1行,输出后一个字符串在前一个字符串中的位置,如果不匹配,则输出0

Sample Input

string str
thisisalongstring isa
nosubstring subt

Sample Output

1
5
0

HINT

提示:

表示字符串的数据结构依然是字符数组。

总结:

KMP算法调用很简单,但难的是理解算法的思想。掌握算法的思想才能说是掌握算法。

Source

[Submit][Status]