最新消息:点击查看大S的省钱秘笈

手算KMP匹配的Next值和Nextval值

编程相关 Slyar 357浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。

计算前缀 Next[i] 的值:

我们令 next[0] = -1 。从 next[1] 开始,每求一个字符的 next 值,就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是,这2个"字符串"不能是同一个"字符串")。如果一个都没有,这个字符的 next 值就是0;如果有,就看它有多长,这个字符的 next 值就是它的长度。

计算修正后的 Nextval[i] 值:

我们令 nextval[0] = -1。从 nextval[1] 开始,如果某位(字符)与它 next 值指向的位(字符)相同,则该位的 nextval 值就是指向位的 nextval 值(nextval[i] = nextval[ next[i] ]);如果不同,则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。

举个例子:

手算kmp的next和nextval

计算前缀 Next[i] 的值:

next[0] = -1;定值。
next[1] = 0;s[1]前面没有重复子串。
next[2] = 0;s[2]前面没有重复子串。
next[3] = 0;s[3]前面没有重复子串。
next[4] = 1;s[4]前面有重复子串s[0] = 'a'和s[3] = 'a'。
next[5] = 2;s[5]前面有重复子串s[01] = 'ab'和s[34] = 'ab'。
next[6] = 3;s[6]前面有重复子串s[012] = 'abc'和s[345] = 'abc'。
next[7] = 4;s[7]前面有重复子串s[0123] = 'abca'和s[3456] = 'abca'。

计算修正后的 Nextval[i] 值:

nextval[0] = -1;定值。
nextval[1] = 0;s[1] != s[0],nextval[1] = next[1] = 0。
nextval[2] = 0;s[2] != s[0],nextval[2] = next[2] = 0。
nextval[3] = -1;s[3] == s[0],nextval[3] = nextval[0] = -1。
nextval[4] = 0;s[4] == s[1],nextval[4] = nextval[1] = 0。
nextval[5] = 0;s[5] == s[2],nextval[5] = nextval[2] = 0。
nextval[6] = -1;s[6] == s[3],nextval[6] = nextval[3] = -1。
nextval[7] = 4;s[7] != s[4],nextval[7] = next[7] = 4。

转载请注明:Slyar Home » 手算KMP匹配的Next值和Nextval值

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (6)

  1. 貌似这个求next好理解. GetNext(const char *T,int next[]) { next[0]=-1; int j=0,k=0; while(T[j]!='') { next[j]=k; if(T[j]==T[k]) ++k; else if (T[j]==T[0]) k=1; else k=0; ++j; } } 但是求nextval就头大了...
    wangjieest5年前 (2012-02-21)回复
  2. 谢谢你~
    FLex5年前 (2011-08-28)回复
  3. @ 没错啊...我按我的算过是这个结果,你觉得答案是多少呢? a b a a b c a c -1 0 0 1 1 2 0 1 a b a a b a a c -1 0 0 1 1 2 3 4
    Slyar7年前 (2009-08-13)回复
  4. 你的解释有问题啊,或是说有一种情况没有解释到,就是你算出的next值会不会下降?按照你的说法,“就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等”,每一位的next值至少等到前面的值啊。比方说这两个例子(1)abaabcac(2)abaabaac,你认识应该是多少?
    匿名7年前 (2009-08-13)回复
  5. @rayleigh 哈,是出了点问题,不过不是你说的那种~谢谢啦,我已经修正了
    Slyar7年前 (2009-08-10)回复
  6. 同学,貌似你这行: nextval[6] = -1;s[6] == s[3],nextval[6] = next[3] = -1。 算错了吧? 应该是 nextval[6] = -1;s[6] == s[3],nextval[6] = next[3] = 0。 你把next[3]的值看成 nextval[3]的值了。 P.S.我是根据数据结构理论看的,没有实际写代码试验,如果出错请见谅
    rayleigh7年前 (2009-08-10)回复