首页 > 试题广场 >

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

备注:
保证字符集为小写字母

这道题你会答吗?花几分钟告诉大家答案吧!