阮一峰的
字符串匹配的KMP算法中详细解释了前缀、后缀的概念,但是没有提到next数组的求法。虽然July的
从头到尾彻底理解KMP(2014年8月22日版)中详细解释了next数组的求法,但是关于k = next[k]这一块讲的还不是太好。下面,我啰嗦几句,咳咳。(ps:往下阅读前建议先看July的那篇文章)
模式字符串记为P(下标从0开始),next[q] = k 表示 P[q]之前的子串中,存在长度为k的相同前缀和后缀 ,即P[0]~P[k-1]与P[q-k]~P[q-1]依次相同。如果P[k] = P[q],那么next[q+1] = k+1,此时表示 P[q+1]之前的子串中,存在长度为k+1的相同前后缀, 这应该不成问题。下面贴张图详细表示: