首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
已知KMP串匹配算法中,子串为babababaa,写出nex
[问答题]
已知KMP串匹配算法中,子串为babababaa,写出next数组与改进后的next数组信息值(要求写出数组下标起点)。
添加笔记
求解答(0)
邀请回答
收藏(3)
分享
纠错
1个回答
添加回答
3
一包薯条呸呸
先给出答案
j
1
2
3
4
5
6
7
8
9
子串T
b
a
b
a
b
a
b
a
a
next[j]
0
1
1
2
3
4
5
6
7
nextval[j]
0
1
0
1
0
1
0
1
7
next 数组推导过程
子串下标起点为1(即T[1] = 'b')
当 j = 1 时,next[1] = 0;
当 j = 2 时,next[2] = 1;
当
j = 3 时,j 由 1 到 j - 1 的串是 "
b
a
",前缀字符 "b" 与 后缀字符 "a" 不相等,next[3] = 1;
当 j = 4 时,j 由 1 到 j - 1 的串是 "
b
ab",前缀字符 "b" 与 后缀字符 "b" 相等,next[4] = 2;
当
j = 5 时,j 由 1 到 j - 1 的串是 "
ba
ba",前缀字符 "ba" 与 后缀字符 "ba" 相等,next[5] = 3;
当
j = 6 时,j 由 1 到 j - 1 的串是 "
ba
b
ab",前缀字符 "bab" 与 后缀字符 "bab" 相等,next[6] = 4;
当
j = 7 时,j 由 1 到 j - 1 的串是 "
ba
b
a
ba",前缀字符 "baba" 与 后缀字符 "baba" 相等,next[7] = 5;
当
j = 8 时,j 由 1 到 j - 1 的串是 "
ba
b
a
b
ab",前缀字符 "babab" 与 后缀字符 "babab" 相等,next[8] = 6;
当
j = 9 时,j 由 1 到 j - 1 的串是 "
ba
b
a
b
a
ba",前缀字符 "bababa" 与 后缀字符 "bababa" 相等,next[9] = 7;
nextval 数组推导过程
子串下标起点为1(即T[1] = 'b')
当 j = 1 时,nextval[1] = 0;
当 j = 2 时,因第二位字符 "a" 在 next 数组中的值是 1,而第一位是 "b" ,它们不相等,所以 nextval[2] = next[2] = 1,维持原值;
当 j = 3 时,因第三位字符 "b" 在 next 数组中的值是 1,与第一位比较得知它们相等,所以 nextval[3] = nextval[1] = 0;
当
j = 4 时,因第四位字符 "a" 在 next 数组中的值是 2,与第二位比较得知它们相等,所以 nextval[4] = nextval[2] = 1;
当
j = 5 时,因第五位字符 "b" 在 next 数组中的值是 3,与第三位比较得知它们相等,所以 nextval[5] = nextval[3] = 0;
当
j = 6 时,因第六位字符 "a" 在 next 数组中的值是 4,与第四位比较得知它们相等,所以 nextval[6] = nextval[4] = 1;
当
j = 7 时,因第七位字符 "b" 在 next 数组中的值是 5,与第五位比较得知它们相等,所以 nextval[7] = nextval[5] = 0;
当
j = 8 时,因第八位字符 "a" 在 next 数组中的值是 6,与第六位比较得知它们相等,所以 nextval[8] = nextval[6] = 1;
当
j = 9 时,因第九位字符 "a" 在 next 数组中的值是 7,而第七位是 "b" ,它们不相等,所以 nextval[9] = next[9] = 7,维持原值;
编辑于 2018-06-13 16:14:33
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
字符串
上传者:
阿奻_
难度:
1条回答
3收藏
3427浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
对于小红书,创作者和粉丝之间互相不...
需求分析
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题