问题描述

KMP算法中的前缀函数问题

复习算法与数据结构这课的KMP算法，到现在对前缀函数很困惑。各位大牛们就举个例子来说说吧。
字符串"abcaababc" 求其KMP前缀函数。
我求出来next[i]：{-1,0,0，-1,1,0,2,0,0}，这是不是KMP前缀函数啊？

解决方案

假设给定的模式串是：abcdabd， 从左到右遍历整个模式串，那么各个子串的前缀后缀为：
子串 前缀 后缀 最大公共长度
a null null 0
ab a b 0
abc a, ab c, bc 0
abcd a, ab, abc d, cd, bcd 0
abcda a, ab, abc, abcd a, da, cda, bcda 1 (存在相同前后缀子串a)
abcdab a, ab,abc,abcd,abcda b,ab,dab,cdab,bcdab 2(相同子串ab)
abcdabd a,ab,abc,abcd,abcda,abcdab d,bd,abd,dabd,cdabd,bcdabd 0

那么子串对应各个前缀后缀公共元素最大长度为：
0, 0, 0, 0, 1, 2, 0
因为模式串首尾会重复:
所以next数组 = 公共元素最大长度整体向右移一位，然后将初值赋为-1
所以模式串 "abcdabd" 的next数组为：-1，0，0，0，0，1，2

解决方案二：

或者是{0,0,0,1,1,2,1,2,3}

解决方案三：

KMP算法中的前缀函数
【算法讲解】前缀函数（KMP的next函数）