首页 > 试题广场 >

已知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)