KMP算法之前感覺(jué)已經(jīng)理解了，但過(guò)了一段時(shí)間，感覺(jué)又不知是什么，現(xiàn)在重新學(xué)習(xí)下，做下記錄。

目的：匹配字符串遇到不匹配的時(shí)候不用回溯，而是通過(guò)一個(gè)數(shù)組（next[]/nextval[]）確定主串不匹配字符接下來(lái)和匹配串哪個(gè)位置的字符進(jìn)行比較。（假設(shè)位置都從0開始） 此時(shí)匹配到6位置，發(fā)現(xiàn)不匹配

匹配串滑動(dòng)盡可能的遠(yuǎn)的距離

實(shí)際上是找到匹配串不匹配位置（6）前的字符串即abadab前綴串和后綴串的最大公共部分的位置

可以看出，abadab的最大公共部分是ab，所以主串位置6的字符d需要和匹配串位置1后面的字符a比較

繼續(xù)比較字符的位置=前綴后綴串最大公共部分的長(zhǎng)度（ab的長(zhǎng)度為2，b的位置是2-1，b后面字符的位置為2-1+1=2）

現(xiàn)在求數(shù)組next[]，設(shè)匹配串是s[0…n] next[0]=-1，-1代表主串某字符和匹配串第一個(gè)字符匹配失敗 next[1]=0 , 一個(gè)字符的沒(méi)有前綴和后綴，其長(zhǎng)度為0 假設(shè)next[i] = x ，即匹配串0到j(luò)-1前后綴的最大公共部分是0到x-1,此時(shí)串的狀態(tài)見圖

現(xiàn)在求next[i+1],即求0到i前后綴的最大公共部分，其組成必定是下圖這樣的，相當(dāng)于求 位置0到i-1字符串的前后綴的公共部分 && s[i]==s[?]成立的最大長(zhǎng)度

當(dāng)位置i和位置x的字符相等時(shí)，顯然？=x，最大公共部分長(zhǎng)度為x+1， 當(dāng)位置i和位置x的字符不相等時(shí)，即長(zhǎng)度為x的公共串不符合要求，需要取相對(duì)小些的公共部分，這個(gè)肯定也是0到x-1的前后綴最大公共部分，即next[x],此時(shí)next[i]和next[?]（此時(shí)？=next[x]）進(jìn)行比較，不相等表示還要取更小的公共部分（即0到next[x]-1的前后綴最大公共部分），重復(fù)這個(gè)過(guò)程，直至s[i]==s[?]或者?==-1為止，-1代表找不到公共部分，即next[i]=0

現(xiàn)在發(fā)現(xiàn)個(gè)問(wèn)題，比如next[i]=x,表示的是主串與匹配串匹配是在匹配串的位置i處發(fā)現(xiàn)不匹配，然后匹配串盡量右移，使主串的那個(gè)字符與匹配串的位置x的字符進(jìn)行比較，如果匹配串位置x的字符和位置i的字符一樣呢，肯定又是不匹配，主串字符再與匹配串位置next[x]的字符進(jìn)行匹配，這不是浪費(fèi)次數(shù)嘛

現(xiàn)在可以改進(jìn)一下數(shù)組next,即當(dāng)s[i]和s[next[i]]一樣時(shí)，next[i]=next[next[i]],這個(gè)就是nextval[]數(shù)組

KMP函數(shù)