首页 > 试题广场 >

KMP算法

[编程题]KMP算法
  • 热度指数：3588 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-1
若出现了多次，则按照升序输出所有出现位置
[要求]
时间复杂度为

输入描述:
第一行一个字符串str
第二行一个字符串match


输出描述:
输出若干个数，分别为match在str中出现的位置，从0开始标号。
若不存在输出-1
示例1

输入

acbc
bc

输出

2
示例2

输入

acbc
bcc

输出

-1
示例3

输入

ababab
ab

输出

0 2 4

备注:
保证字符集为小写字母
算法知识视频讲解
开通博客
头像 wolf鬼刀
发表于 2020-08-30 13:05:26
题目描述给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-1若出现了多次，则按照升序输出所有出现位置 [要求]时间复杂度为O(n)O(n) 输入描述:第一行一个字符串str第二行一个字符串mat 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Huster水仙
发表于 2023-01-08 16:39:51
/*KMP算法核心思想并不难，但是各种版本总有细小的区别 每次复习都会产生疑问，又重蹈覆辙才豁然开朗 next数组： 目的：当子串pattern[i]不匹配时，转到next[i]继续匹配，从而保证主串不回溯 求解：next[i]的值即为pattern[0]~patte 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Jim-zht
发表于 2022-03-15 11:37:00
KMP算法的两个步骤： 先找出nextArray，记录的是前面的项，前缀等于后缀的最大长度。 再根据nextArray数组，计算往前跳转的位置。 以上两个步骤中，均有判断nextArray[m] == -1这一项。
去ta的博客 赞 (0) 回复(0) 收起

问题信息

字符串
上传者：小小
难度：
10条回答 4466浏览

热门推荐

通过挑战的用户

查看代码

相关试题

KMP算法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号