看毛片（kmp）算法next数组部分详解
本帖最后由 hqgxx 于 2016-4-15 00:17 编辑我的目的是详细介绍小甲鱼视频中的next怎么求，因为小甲鱼说有很多朋友卡在这个上面了。(视频39集，KMP算法之NEXT数组代码原理分析)
第一步：假设next=5，主串为S，next到next已经求出来了。
第二步：当是S到S和T到T相等时，S!=T时，T就要回溯到5。使S对应T.
第三步：所以S对应着T,因为S=T,所以T对应着T.
第四步：然而S!=T,所以T要回溯到T。
第五步：T和S（S=T）比较,很明显不相等，所以T要回溯到T.
第六步 :T和S(S=T)比较，很明显相等。
第七步：所以，S!=T时，T要和S对应，所以T就和S对应了。
最终结论，S!=T时，T的next等于2；也就是说T要回溯到2的位置。
别看我用了主串，其实next数组和主串没有关系，只是为了方便理解，才引用了主串。至于为什么，你可以画两个字符串，按照我上面说的，多尝试几次，就知道了。
f:\QQ图片20160414232505
页:
[1]