KMP算法的int[] next数组的“首位”与“第二位”的“最大前后缀”问题。(本人的next[]数组中的值就是最大前后缀的长度)
(说明:本人只是单纯记录一下突然想明白的事情,如果有写的不好或者不正确的地方还请饶过!)
1.结论:首位的最大前后缀是-1很重要!!!!,不然KMP算法在i=i-next[j]在第一个元素不相等时,会陷入死循环。
其实首位也不一定非要为-1,也可以是0,但这时,第二位的最大前后缀长度应该为1。
总而言之就是,首位和第二位的最大前后缀不能相等,前者要比后者少1。
2.分析原因:
其实首位的最大前后缀肯定是没有,因为其前面没有元素了。第二位的最大前后缀肯定也没有,因为第二位前面就1一个(首位)元素
那么,为什么首位和第二位的前后缀不能相等为0呢?
因为在后面KMP算法中如果在“比对串的[j]位置”检测到与“主串相对应的[i]位置上”不等时,那么i应该通过next[j]来做到“回溯”,即i = i - next[j]
此时,①.若j=1时,next[j]=next[1]=0(next[1]必然是没有最大前后缀的),i=i-next[j]=i-0=i,即:i从目前位置再与“比对串的头部开始配对”
②.若j=0时,此时假设next[j]=next[0]=0,i=i-next[j]=i-0=i,即:i从目前位置再与“比对串的头部开始配对”
看到①和②感觉是不是还是看不出什么问题?但如果仔细想一想就会发现,②会陷入死循环,因为i一直在“原地踏步”,那为什么①“看似”和②“写的一样”呀,
那①岂不也陷入死循环?
其实不然!!!!仔细分析会发现因为①中j=1,即“比对串”此时走在了“第二个元素”上(索引下标从0开始嘛),那么也就是主串i此时也是往后挪了一位
(“比对串j=0”和“主串i”相比 且 相等,“比对串j=1”和“主串i+1”相比 且 不等),所以,尽管此时第个字符比对不相等时,i=i-next[j]=i-next[1]=i-0=i
也并不是“原地踏步”,而是在比对的过程(第一个字符比对相等后)中已经往后走了一步。