看毛片（kmp）算法next数组部分详解

hqgxx

我的目的是详细介绍小甲鱼视频中的next[7]怎么求，因为小甲鱼说有很多朋友卡在这个上面了。(视频39集，KMP算法之NEXT数组代码原理分析)
第一步：假设next[7]=5，主串为S，next[1]到next[6]已经求出来了。
第二步：当是S[1]到S[6]和T[1]到T[6]相等时，S[7]!=T[7]时，T就要回溯到5。使S[7]对应T[5].
第三步：所以S[6]对应着T[4],因为S[6]=T[6],所以T[6]对应着T[4].
第四步：然而S[6]!=T[4],所以T要回溯到T[2]。
第五步：T[2]和S[6]（S[6]=T[6]）比较,很明显不相等，所以T要回溯到T[1].
第六步 :T[1]和S[6](S[6]=T[6])比较，很明显相等。
第七步：所以，S[7]!=T[7]时，T[1]要和S[6]对应，所以T[2]就和S[7]对应了。

最终结论，S[7]!=T[7]时，T[7]的next等于2；也就是说T要回溯到2的位置。

别看我用了主串，其实next数组和主串没有关系，只是为了方便理解，才引用了主串。至于为什么，你可以画两个字符串，按照我上面说的，多尝试几次，就知道了。
f:\QQ图片20160414232505