计算数据结构KMP算法next、nextval值（仅有求值过程。不包含原理）

KMP算法求next数组值流程

1. 添加字符序号j（序号从1开始）和next数值（默认前两位的数值为0、1）

2.计算字符的next值需要使用上一位字符与其next值相对应的字符进行比较，若相同则其next值为上一位的next值+1，比较结束，若不同则继续向下比较，若向下比较时有相同字符，则取相同字符上一位字符的next值加一，直到第一位结束，若无匹配则取next默认值（默认为1） 

例：

1.已知串S=’aaab'，其Next数组值为（）

A.0123

B.1123

C.1231

D.1211

计算第三位字符 a([  3字符序号）    a(字符）      ?(该字符对应的next值）]) 

        需要第二位字符a ([2 a 1]) 与其next值指向的字符比较，第二位字符next值为1，即指向字符序号为一的 a[1 a 0 ] 比较  ，第二位字符 a 与 第一位字符 a 相等，第三位字符next值为第二位字符的next值 1   +   1   = 2

同理 可获取第四位字符的next值,第三位字符a（[3 a 2]）,指向第二位字符a（[2 a 1]）,第三位字符a 与第二位字符 a相同 ,第四位的next值为 第三位next值加一 即2+1 = 3

字符串S的next值为 0 1 2 3 

故答案为A

next

2.串‘ababaaababaa’的next数组为（）

A.012345678999

B.012121111212

C.011234223456

D.0123012322345

做法与上一题相同

图片版本：

文字版本：

{

1.先写字符的序号

2.写第一位第二位字符的默认next值 0，1

求第三位字符的next值，取前一位（第二位字符）[2 b 1],对应第一位字符[1 a 0], 字符不相同(b与a不相同),继续向下比较，但已经比较到字符串首，比较结束，第三位字符的next值取默认值1

求第四位字符的next值，取前一位（第三位字符）[3 a 1],对应第一位字符[1 a 0],字符相同（a与a相同），第四位字符的next值为第三位next值1+1 =2

求第五位字符的next值，取前一位（第四位字符）[4 b 2],对应第二位字符[2 b 1],字符相同（b与b相同) ，第五位字符的next值为第四位next值2+1=3

求第六位字符的next值，取前一位（第五位字符）[5 a 3],对应第三位字符[3 a 1],字符相同（a与a相同) ，第六位字符的next值为第五位next值3+1=4

求第七位字符的next值，取前一位（第六位字符）[6 a 4],对应第四位字符[4 b 2],字符不相同（a与b不相同) ，继续取第三位字符[4 b 2]对应的第二位字符[2 b 1]比较，字符不相同(a与b不相同)，继续取第二位字符[2 b 1]对应的第一位字符[1 a 0]比较，字符相同（a与a相同），取第一位字符的上一位字符[2 b 1]的next+1 得第七位字符的next值 为1+1 =2

求第八位字符的next值，取前一位（第七位字符）[7 a 2],对应第二位字符[2 b 1],字符不相同（a与b不相同) ，继续取第二位字符[2 b 1]对应的第一位字符[1 a 0]比较，字符相同（a与a相同），取第一位字符的上一位字符[2 b 1]的next值+1 得第八位字符的next值 为1+1 =2

求第九位字符的next值，取前一位（第八位字符）[8 b 2]，对应第二位字符[2 b 1]，字符相同（b与b相同），第九位字符的next值为2+1 = 3 

求第十位字符的next值，取前一位（第九位字符）[9 a 3]，对应第三位字符[3 a 1]，字符相同（a与a相同），第十位字符的next值为3+1 =4

求第十一位字符的next值，取前一位（第十位字符）[10 b 4]，对应第四位字符[4 b 2]，字符相同（b与b相同），第是十一位字符的next值为4+1=5

求第十二位字符的next值，取前一位（第十一位字符）[11 a 5]，对应第五位字符[5 a 3]，字符相同（a与a相同），第十二位字符的next值位5+1 = 6

最后得到串'ababaaabaabaa’的next数组为011234223456

答案为C

}

next

nextval（next函数修正值）的计算

nextval的计算需要先算出串的next值

3.字符串‘ababaabab’的nextval值为（）

A.(0,1,0,1,0,4,1,0,1)

B.(0,1,0,1,0,2,1,0,1)

C.(0,1,0,1,0,0,0,1,1)

D.(0,1,0,1,0,1,0,1,1)

先计算串‘ababaabab’的next值

与上两题做法相同，可以求出next值为 011234234

1. 添加字符序号j（序号从1开始），字符以及其对应的next数值，nextval数值（第一位 默认为0）

2.计算字符的nextval值是 用其字符和其字符next值所对应的字符进行比较  相同则继续向下比较取最后一位的next值，若不同则取其自己的next值，

例:

第二位字符的nextval 为其字符b（[2 b 1]）与其next值对应的第一位字符 a（[1 a 0])比较，字符不相同（b与a不相同），则取其自己的next值做nextval值 = 1

第三位字符的nextval为其字符a（[3 a 1]）与其next值对应的第一位字符a（[1 a 0]）比较，字符相同（a与a相同），继续向下比较，但已经到达字符串首，比较结束，取其对应字符([1 a 0])的next值 =0

第四位字符的nextval为其字符b（[4 b 2]）与其next值对应的第二位字符b（[2 b 1]）比较，字符相同（b与b相同），继续向下比较，取第二位字符b（[2 b 1]）next值对应的字符a（[1 a 0]）比较，字符不相同（b与a不相同），比较结束，取第二位字符的next值为第四位的nextval = 1

第五位字符的nextval为其字符a（[5 a 3]）与其next对应的第三位字符a（[3 a 1]）比较，字符相同（a与a相同），继续向下比较，取第三位字符a（[3 a 1]）next值对应的字符a（[1 a 0 ]）比较，字符相同（a与a相同），已到达字符串首，取第一位字符串a（[1 a 0]）对应的next值作为第五位字符的nextval值  = 0

第六位字符的nextval为其字符a（[6 a 4]）与其next值对应的第四位字符b（[4 b 2]）比较，字符不相同（a与b不相同），取其自己的next值做nextval值 = 4

第七位字符的nextval 为其字符b（[7 b 2]）与其next值对应的第一位字符 b（[2 b 1])比较，字符相同（b与b相同），继续向下比较，取第二位字符b（[2 b 1]）next值对应的字符a（[1 a 0]）比较，字符不相同（b与a不相同），比较结束，取第二位字符的next值为第七位的nextval = 1

第八位字符的nextval为其字符a（[8 a 3]）与其next对应的第三位字符a（[3 a 1]）比较，字符相同（a与a相同），继续向下比较，取第三位字符a（[3 a 1]）next值对应的字符a（[1 a 0 ]）比较，字符相同（a与a相同），已到达字符串首，取第一位字符串a（[1 a 0]）对应的next值作为第八位字符的nextval值 = 0

第九位字符的nextval为其字符b（[9 b 4]）与其next值对应的第四位字符b（[4 b 2]）比较，字符相同（b与b相同），继续向下比较，取第四位字符b（[4 b 2]）与其next值对应的第二位字符b（[2 b 1]）比较，字符相同（b与b相同），继续向下比较，与其next值对应的字符a（[1 a 0]）比较，字符不相同（b与a不相同），

比较结束，取第二位字符的next值为第九位的nextval = 1

得出其nextval值为010104101

答案为A

nextval

4.模式串t ='abcaabbcabcaabdab’,该模式串的next数组的值为（），nextval数组的值为（）

A 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2

B 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2

C 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1

D 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2

E  0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1

F  0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1

根据上题做法可解得

答案 DF

next

nextval