当前位置:首页 > 字符串 > 正文
洛谷P3375【模板】KMP字符串匹配
4189+

题目大意:两个字符串a和b,请将b在a中出现的所有位置输出来,并输出next数组。

题目描述

如题,给出两个字符串s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置。

为了减少骗分的情况,接下来还要输出子串的前缀数组next。如果你不知道这是什么意思也不要问,去百度搜[kmp算法]学习一下就知道了。

输入输出格式

输入格式:

第一行为一个字符串,即为s1(仅包含大写字母)

第二行为一个字符串,即为s2(仅包含大写字母)

输出格式:

若干行,每行包含一个整数,表示s2在s1中出现的位置

接下来1行,包括length(s2)个整数,表示前缀数组next[i]的值。

输入输出样例

输入样例#1:

ABABABC
ABA

输出样例#1:

1
3
0 0 1 

说明

时空限制:1000ms,128M

数据规模:

设s1长度为N,s2长度为M

对于30%的数据:N<=15,M<=5

对于70%的数据:N<=10000,M<=100

对于100%的数据:N<=1000000,M<=1000

解题思路

1、前缀:以首字符开头的连续的字符,不包括自己,如abcd的前缀有a、ab、abc。

2、后缀:后末字符结尾的连续的字符,不包括自己,如abcd的后缀有d、cd、bcd。

3、next数组:next[i]表示0到i的字符串的最长公共前后缀的长度。

4、在匹配失败时,如果存在公共前后缀,则这部分字符不需要再比较了。

5、next数组代码解释:j是b串当前字符,i是公共前后缀的下一个字符。如果a[i]==b[j],那么公共前后缀长度多1,也即i+1;如果不相同,则找公共前后缀长度小一些的,即看一下第c[i-1]个字符是否跟b[j]相同。例子:abadabab,在计算最后一个字符的next值时,i=3,j=7,c[i-1]=1……

6、KMP代码解释:i是a串当前字符,j是b串当前字符,如果两个字符相同,则继续比较后一位;否则,看一下是否有公共前后缀,有的话直接比较公共前后缀的下一个字符。

程序实现

About

坚决不Copy代码!

本文标签:,,,

洛谷P3375【模板】KMP字符串匹配:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!