KMP算法（學習記錄）

2019-11-10 18:11:14

字體：大中小

來源：轉載

供稿：網友

KMP算法之前感覺已經理解了，但過了一段時間，感覺又不知是什么，現在重新學習下，做下記錄。

目的：匹配字符串遇到不匹配的時候不用回溯，而是通過一個數組（next[]/nextval[]）確定主串不匹配字符接下來和匹配串哪個位置的字符進行比較。（假設位置都從0開始）匹配過程此時匹配到6位置，發現不匹配

這里寫圖片描述匹配串滑動盡可能的遠的距離

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

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

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

現在求數組next[]，設匹配串是s[0…n] next[0]=-1，-1代表主串某字符和匹配串第一個字符匹配失敗 next[1]=0 , 一個字符的沒有前綴和后綴，其長度為0 假設next[i] = x ，即匹配串0到j-1前后綴的最大公共部分是0到x-1,此時串的狀態見圖這里寫圖片描述

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

這里寫圖片描述

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

// 輸入s[0...n] 空數組next[0...n] 求next[] int i=0,x=-1; next[i]=x; while(i<=n) { if(x==-1 || s[i]==s[x]) next[++i]=++x; else x=next[x]; }

現在發現個問題，比如next[i]=x,表示的是主串與匹配串匹配是在匹配串的位置i處發現不匹配，然后匹配串盡量右移，使主串的那個字符與匹配串的位置x的字符進行比較，如果匹配串位置x的字符和位置i的字符一樣呢，肯定又是不匹配，主串字符再與匹配串位置next[x]的字符進行匹配，這不是浪費次數嘛這里寫圖片描述

現在可以改進一下數組next,即當s[i]和s[next[i]]一樣時，next[i]=next[next[i]],這個就是nextval[]數組

這里寫圖片描述

// 輸入s[0...n] 空數組nextval[0...n] 求nextval[] int i=0,x=-1; nextval[i]=x; while(i<=n) { if(x==-1 || s[i]==s[x]) { ++i;++x; if(s[i]==s[x]) nextval[i]=nextval[x];//增加一個判斷即可 else nextval[i]=x; } else x=next[x]; }

KMP函數

//輸入str[0...size] s[0....n] int i=0;j=0; while[i<=size && j<=n] { if(j==-1 || str[i]==s[j]){++i;++j;} else j=nextval[j]; } if(j>n) return i-n-1;//匹配成功 else return -1; //匹配失敗

這里寫圖片描述