理解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]?
恕我愚钝,还请帮忙,给出针对以上问题的解释。
奖励如果不满意,可追加。谢谢!