必威体育Betway必威体育官网
当前位置:首页 > IT技术

Next 值与 Nextval 值的计算

时间:2019-05-31 17:44:05来源:IT技术作者:seo实验室小编阅读:78次「手机版」
 

nextval

KMP算法对模式串求解其Next值和nextval值的计算方法


    • Next值的计算
      • 方法一
      • 方法二
    • Nextval值的计算


模式串S = “abaabcac” ,求其 Next 数值序列

1 2 3 4 5 6 7 8
a b a a b c a c

Next值的计算

Next值的计算,首先将串的字符进行标号,如下:

第一位的Next值为 0

第二位的Next值为 1

1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2

方法一

标准求解方法

  • 第三位:前一位(第二位)的Next值为1 → 1对应的标号1的字符为a → (第二位)的字符b与标号1的字符a不同 → 但无法再找前一位匹配 → 所以第三位是 1

  • 第四位:前一位(第三位)的Next值为1 → 对应标号字符为a → (第三位)的字符a与标号1的字符a相同 → 第四位Next值为第三位的Next值+1 = 2

  • 第五位:前一位(第三位)的Next值为2 → 对应标号字符为b → (第四位)的字符a与标号2的字符b不同 → b的Next值为1 → 对应标号字符aa与(第四位)字符相同 → 第五位Next 值为第二位**b**Next值1+1=2

  • 第六位:前一位(第五位)的Next值为2 → 对应标号字符为b → (第五位)的字符b与标号2的字符b相同 → 第六位Next值为第五位的Next值+1 = 3

  • 第七位:前一位(第六位)的Next值为3 → 对应标号字符为a → (第六位)的字符c与标号3的字符a不同 → a的Next值为1 → 对应标号字符aa与(第四位)字符不同 → 但由于已经匹配到头 → 第七位的Next 值为1

  • 第八位:前一位(第七位)的Next值为1 → 对应标号字符为a → (第七位)的字符a与标号1的字符a相同 → 第八位Next值为第七位的Next值+1 = 2

方法二

刷题时遇到的别人的解法,感觉很不错,记录一下

简述:Next 值就是字符串s的最长相同前缀和后缀子字符串的长度

1 2 3 4 5
b a b a b
0 1

首先前两位0、1 是固定不变的

- 第三位:字符串是”bab”,前缀有b, ba;后缀有ab,b,前后缀相等的最长字符串为b,长度为1,所以第三位Next值为1

- 第四位:字符串”baba”,前缀有b, ba, bab;后缀有aba, ba, a,前后缀相等的最长字符串为ba,长度为2,所以第三位Next值为2

- 第五位:字符串”babab”,前缀有b, ba, bab, baba;后缀有abab, bab, ab, b,前后缀相等的最长字符串为bab,长度为3,所以第三位Next值为3

注:经验证:使用方法二算出的S = “abaabcac”的Next值与使用方法一得到的值不同,所以方法二的正确性待确定

Nextval值的计算

Nextval是对Next的优化

**简述:**NextVal值就是字符串s的的最长相同且满足后续字符不同的前缀和后缀子字符串的长度。

上述字符串计数时时从1开始计数,那么从零开始的呢?

- 首先可以看到从 1 开始的,其 Next 值为:

i 1 2 3 4 5 6 7 8 9
s a b a b a a b a b
Next[i] 0 1 2 2 3 4 2 3 4

- 然后从 0 开始的,Next 值为:

i 0 1 2 3 4 5 6 7 8
s a b a b a a b a b
Next[i] -1 0 0 1 2 3 1 2 3
Nextval[i] -1 0 -1 0 -1 3 0 -1 0

注意:可以看出,Next 值并不是第一个求得的值依次减一所对应的。

C2CrrD.jpg

过程详述

- Nextval[0] = -1 ,和Next[0]的值一样

- Nextval[1] ,Next[1] = 0 , s[0] = a ,a ≠ b(s[1]),则Nextval[1] = Next[1] = 0

- Nextval[2] ,Next[2] = 0 , s[0] = a ,a = a(s[2]),则Nextval[1] = Nextval[0] = -1

- Nextval[3] ,Next[3] = 1 , s[1] = b ,b = b(s[3]),则Nextval[3] = Nextval[1] = 0

- Nextval[4] ,Next[4] = 2 , s[2] = a ,a = a(s[4]),则Nextval[4] = Nextval[2] = 0

- Nextval[5] ,Next[5] = 3 , s[3] = b ,b ≠ a(s[5]),则Nextval[5] = Next[5] = 3

- Nextval[6] ,Next[6] = 1 , s[1] = b ,b = b(s[6]),则Nextval[6] = Nextval[1] = 0

- Nextval[7] ,Next[7] = 2 , s[2] = a ,a = a(s[7]),则Nextval[7] = Nextval[2] = -1

- Nextval[8] ,Next[8] = 3 , s[3] = b ,b = b(s[8]),则Nextval[8] = Nextval[3] = 0

相关阅读

什么是计算机二进制

很多专业人士从第一次学计算机,就开始接触二进制,发现书上说的基本都是术语,不是“人话”,马上晕倒。二进制是什么?什么“逢二进一”,这

Amazon的云计算(1)——基础存储架构Dynamo

Amazon 依靠在电子商务中积累的大量基础性设施和各类先进技术,很早地进入了云计算领域,并在提供计算、存储等服务方面处于领先地位

计算机专业考研复习计划指导与建议

作为一名21世纪标准的理工男,计算机方向的专业学生,考研是另一种提升自己的有效路径,本人是计算机科学与技术专业出身,也是通过考研从

System.currentTimeMillis()计算方式与时间的单位转换

一、时间的单位转换1秒=1000毫秒(ms) 1毫秒=1/1,000秒(s) 1秒=1,000,000 微秒(μs) 1微秒=1/1,000,000秒(s) 1秒=1,000,000,000 纳

BMI计算器

a = 1 b = 2 # 在python3以上版本中 /单除号 若两侧为整数,计算会得到小数,如果想要得到整数,可以使用// 双除号 # 在python3以下版

分享到:

栏目导航

推荐阅读

热门阅读