Dotcpp  >  编程题库  >  数据结构-KMP字符串模式匹配算法实现
题目 1691:

数据结构-KMP字符串模式匹配算法实现

时间限制: 1s 内存限制: 32MB 提交: 544 解决: 297

题目描述

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

下面是相应的算法:

KMP算法

图:KMP算法

输入格式

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

输出格式

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

样例输入

string str
thisisalongstring isa
nosubstring subt

样例输出

1
5
0

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签

通过率

统 计