Dotcpp  >  编程题库  >  数据结构-求子串位置的定位函数
题目 1689:

数据结构-求子串位置的定位函数

时间限制: 1s 内存限制: 32MB 提交: 308 解决: 128

题目描述

在算法4-1中已经描述过一种定位子串的算法,但其依赖字符串的其他操作(使用了算法4-3描述的子串提取以及字符串比较)。
下面给出书中另一种相对独立的定位子串算法:
求子串位置的定位函数
图:求子串位置的定位函数
书中的算法思想是这样的:分别利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置。算法的基本思想是:从主串S的第pos个字符起和模式的第一个字符比较之,若相等,则继续逐个比较后续字符,否则从主串的下一个字符起再重新和模式的字符比较之。依次类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则称匹配成功,函数值为和模式T中第一个字符相等的字符在主串中的序号,否则称匹配不成功,函数值为零。
       你的任务是将S中每次比较的字符输出来,并将匹配的序号输出。

输入格式

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

输出格式

每组数据输出2行,第一行是S中每次比较的字符,第二行是后一个字符串在前一个字符串中的位置,如果不匹配,则输出0。

样例输入

string str
thisisalongstring isa
nosubstring subt

样例输出

str
1
thisisisa
5
nosubsubsttring
0

提示

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

视频教学见视频网课

标签

通过率

统 计