今天看KMP算法， 一头雾水！虽然算法的过程是明白了，但是怎么也想不出来怎么证明其中的next函数是怎么得到的。
也就是这个'p⑴ p⑵ p⑶…..p(k-1）’ = ' p(j-k+1）p(j-k+2）……p(j-1）’。 为什么找到这个k以后用k的元素比较字符串中i就行了。

现在找到一个最接近明白的就是百度百科上的

假设
主串：s: ‘s⑴ s⑵ s⑶ ……s(n）’ ;
模式串 ：p: ‘p⑴ p⑵ p⑶…..p(m）’
把课本上的这一段看完后，继续
现在我们假设 主串第i个字符与模式串的第j(j<=m）个字符‘失配’后，主串第i个字符与模式串的第k(k<j）个字符继续比较
此时，s(i）≠p(j），有
主串：s⑴…… s(i-j+1）…… s(i-1） s(i) ………….
|| （相配） || ≠（失配）
匹配串：p⑴ ...........p(j-1） p(j)
由此，我们得到关系式：
‘p⑴ p⑵ p⑶…..p(j-1）’ = ’ s(i-j+1）……s(i-1）’
由于s(i）≠p(j），接下来s(i）将与p(k）继续比较，则模式串中的前（k-1）个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：（k<j),
‘p⑴ p⑵ p⑶…..p(k-1）’ = ’ s(i-k+1）s(i-k+2）……s(i-1）’
即：
主串：s⑴……s(i-k +1） s(i-k +2） ……s(i-1） s(i) ………….
|| （相配） || ||（有待比较）
匹配串：p⑴ p⑵ ……..... p(k-1） p(k)
现在我们把前面总结的关系综合一下
有：
s⑴…s(i-j +1）… s(i-k +1） s(i-k +2） …… s(i-1） s(i) ……
|| （相配） || || || ≠（失配）
p⑴ ……p(j-k+1） p(j-k+2） …...... p(j-1） p(j)
|| （相配） || ||（有待比较）
p⑴ p⑵ ……...... p(k-1） p(k)
由上，我们得到关系：
'p⑴ p⑵ p⑶…..p(k-1）’ = ' p(j-k+1）p(j-k+2）……p(j-1）’

不知道是从哪个课本上抄来的。 其实还是不太明白最后一步。