今天看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）’

不知道是從哪個課本上抄來的。 其實還是不太明白最后一步。