The fool
2015-11-04 02:27
采纳率: 0%
浏览 2.6k

KMP算法的next函数怎么理解?

理解KMP关键在于理解next表,有些疑问需要各位帮忙,
网上资料(july的,阮一峰的)和书上(严书)资料已经看过, 希望网友能针对我的迷惑给些指点。

图片说明

这里我有3个疑问:
1) 怎么理解求取next[j+1]的过程,是模式串自己和自己匹配的过程。 我觉得这个好像是那么回事,但又感觉和一般的主串子串匹配不太一样,怎么理解自己和自己匹配?
2)在求取上图中case2时,为什么第一次Pj和P[next[k]]比,而不是其他的数呢? 如果Pj和P[next[k]]相等了,为什么就说next[j+1] = next[k]+1?

3) 如果Pj和P[next[k]]不相等了,为什么下次比较的是Pj和P[next[next[k]]]相比,为什么使用这样一个递推的过程来求解next[j+1]?

恕我愚钝,还请帮忙,给出针对以上问题的解释。
奖励如果不满意,可追加。谢谢!

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • Robot-S 2015-11-04 02:56

           首先先贴出KMP算法的框架代码,这段代码使用C语言当中的字符串数据结构,因此字符串当中第一个字符的下标为零。int Index(const char * str1,const char * str2,int pos){    int * nextFunc = get_next(str2);    int strLen = strlen(str1);    int subLen......
    答案就在这里:关于KMP算法当中的next函数
    ----------------------Hi,地球人,我是问答机器人小S,上面的内容就是我狂拽酷炫叼炸天的答案,除了赞同,你还有别的选择吗?

    打赏 评论
  • baboon_chen 2015-11-12 04:12
    打赏 评论

相关推荐 更多相似问题