首页 > 试题广场 >

已知KMP串匹配算法中，子串为babababaa，写出nex

[问答题]
已知KMP串匹配算法中，子串为babababaa，写出next数组与改进后的next数组信息值（要求写出数组下标起点）。
添加回答
一包薯条呸呸头像 一包薯条呸呸
先给出答案
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'）
  1. 当 j = 1 时，next[1] = 0;
  2. 当 j = 2 时，next[2] = 1;
  3. 当 j = 3 时，j 由 1 到 j - 1 的串是 "ba"，前缀字符 "b" 与 后缀字符 "a" 不相等，next[3] = 1;
  4. 当 j = 4 时，j 由 1 到 j - 1 的串是 "bab"，前缀字符 "b" 与 后缀字符 "b" 相等，next[4] = 2;
  5. 当 j = 5 时，j 由 1 到 j - 1 的串是 "baba"，前缀字符 "ba" 与 后缀字符 "ba" 相等，next[5] = 3;
  6. 当 j = 6 时，j 由 1 到 j - 1 的串是 "babab"，前缀字符 "bab" 与 后缀字符 "bab" 相等，next[6] = 4;
  7. 当 j = 7 时，j 由 1 到 j - 1 的串是 "bababa"，前缀字符 "baba" 与 后缀字符 "baba" 相等，next[7] = 5;
  8. 当 j = 8 时，j 由 1 到 j - 1 的串是 "bababab"，前缀字符 "babab" 与 后缀字符 "babab" 相等，next[8] = 6;
  9. 当 j = 9 时，j 由 1 到 j - 1 的串是 "babababa"，前缀字符 "bababa" 与 后缀字符 "bababa" 相等，next[9] = 7;
nextval 数组推导过程
子串下标起点为1（即T[1] = 'b'）
  1. 当 j = 1 时，nextval[1] = 0;
  2. 当 j = 2 时，因第二位字符 "a" 在 next 数组中的值是 1，而第一位是 "b" ，它们不相等，所以 nextval[2] = next[2] = 1，维持原值;
  3. 当 j = 3 时，因第三位字符 "b" 在 next 数组中的值是 1，与第一位比较得知它们相等，所以 nextval[3] = nextval[1] = 0;
  4. 当 j = 4 时，因第四位字符 "a" 在 next 数组中的值是 2，与第二位比较得知它们相等，所以 nextval[4] = nextval[2] = 1;
  5. 当 j = 5 时，因第五位字符 "b" 在 next 数组中的值是 3，与第三位比较得知它们相等，所以 nextval[5] = nextval[3] = 0;
  6. 当 j = 6 时，因第六位字符 "a" 在 next 数组中的值是 4，与第四位比较得知它们相等，所以 nextval[6] = nextval[4] = 1;
  7. 当 j = 7 时，因第七位字符 "b" 在 next 数组中的值是 5，与第五位比较得知它们相等，所以 nextval[7] = nextval[5] = 0;
  8. 当 j = 8 时，因第八位字符 "a" 在 next 数组中的值是 6，与第六位比较得知它们相等，所以 nextval[8] = nextval[6] = 1;
  9. 当 j = 9 时，因第九位字符 "a" 在 next 数组中的值是 7，而第七位是 "b" ，它们不相等，所以 nextval[9] = next[9] = 7，维持原值;
编辑于 2018-06-13 16:14:33 回复(0)
提交观点

问题信息

字符串
上传者：阿奻_
难度：
1条回答 3628浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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