KMP算法的核心是利用匹配失敗后的信息简珠，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的外盯。具體實現(xiàn)就是通過一個next()函數(shù)實現(xiàn)麸澜，函數(shù)本身包含了模式串的局部匹配信息哟绊。KMP算法的時間復(fù)雜度O(m+n)。
KMP??????????????????????????模式匹配算法原理
情況1:
例如,假設(shè)現(xiàn)在有一個主串S = “a a acaaab” ; 模式串 T = “aaab” ; 如果使用暴風(fēng)算法的話,前面5個字母完全相等,直到第6個字母.'f' 和 'x' 不相等; 如下圖;
接下來按照爆發(fā)算法,我們需要執(zhí)行的過程.即主串i=2,3,4,5,6時,首字母與子串T的首字母均不相等;
按照爆發(fā)算法的設(shè)計,我們的執(zhí)行過程就是如此. 但是對于要匹配的子串T來說,"abcdex" 首字母"a" 與后面的串"bcdex"中任意一個字符都不相等;
也就是說, 既然"a"不與自己后面的子串中任何一個字符相等. 那么對于上圖中①來說,前面5個字符分別相等.那就意味著子串T與首字符"a"不可能與S 串的第2位到第5位想的.
KMP算法的想法是痰憎，設(shè)法利用這個已知信息，不要把"搜索位置"移回已經(jīng)比較過的位置攀涵，繼續(xù)把它向后移铣耘，這樣就提高了效率
理解KMP 關(guān)鍵
? 如果我們知道 T 串中的首字母"a" 與 T 中后面的字符均不相等(注意這是前提,如何判斷后面會說明);
? 并且 T 串的第二位的 "b" 與 S 串中的第二位的 "b" 在第①圖已經(jīng)判斷相等.
? 那么就意味著. T串中的首字符 "a" 與 S 串中的第二位 "b" 是不需要判斷. 也知道他們不可能相等; 那么圖②是可以省略的!
?同樣的道理，在我們知道T串中首字母“a”與T中的后面字符均不相等的前提以故，T串中的“a”與S串中的“c”“d”“e”也都可以和在于1圖之后就確定時不相等的蜗细，索引2，3，4炉媒，5都是沒必要的踪区；
?只要保留1，6即可如下圖：
? 之所以會保留第⑥次判斷是因為在①中 T[6] != S[6],盡管我們已經(jīng)知道T[1] != T[6]. 但是不能斷定 T[1] 一定不等于 s[6].
情況2:
例如,假設(shè)現(xiàn)在有一個主串S = “abcababca” ; 模式串 T = “abcdex” ;
? 對于開始的判斷,前 5 個字符完全相等. 第6個字符不相等; 如果下圖①
? 根據(jù)剛才的經(jīng)驗,T 的首字符 "a" 與 T的第二位字符 "b" ,第三位字符 "C" 均不相等. 所以不需要做判斷了.那么步驟②③都是多余的;
? 因為 T 的首位"a" 與 T 的第四位的 "a" 相等, 第二位的 "b" 與第五位的 "b" 相等;
? 而且在第①次比較時, 第四位的 "a" 與 第五位的 "b" 已經(jīng)與主串 S 中的相應(yīng)位置比較過了.是相等的;
? 因此可以斷定: T 的首字符 "a", 第二字符 "b" 與 S 的第四位字母"a" 和第五位字母"b" 不需要在做比較了. 肯定也是相等的.
? 所以④⑤的比較也是多余的
? 也就是說,對于子串中有與首字符相等的字符,也是可以省略一部分不必要的判斷步驟;
如下圖所示吊骤，省略了右圖T串前兩位“a”與“b”同S串中的4缎岗，5位置字符匹配操作
? 對比這2個例子中, 我們會發(fā)現(xiàn) ① 時,我們的 i 值,就是主串當前位置的下是 6 ;
? ②③④⑤ ,i 的值是 2,3,4,5, 到了 ⑥ 時,i 值又回到了6.
? 當我們在暴風(fēng)匹配算法中, 主串的 i 值是不斷地回溯來完成的;
? 而在剛剛的分析中,有很多不必要的回溯;
? 而KMP 算法就是為了讓不必要的回溯發(fā)生!
既然 i 值不能回溯, 也不可以變小; 那么考慮的變化就是 j 值;
通過剛剛的分析了解,我們屢次提到了 T 串的首字符 與自身后面字符的比較; 發(fā)現(xiàn)如果有相等字符, j值的變化就會不相同; 也就是說, j 值的變化其實與主串的關(guān)系. 更多取決于T串中的結(jié)構(gòu)是否有重復(fù)問題;
如上圖，由于T=“abcdex”當中沒有重復(fù)的數(shù)字白粉，所以j就又6變成了1传泊；
而下圖，由于T=“abcabx”前綴“ab”與最后的“x”之前串的后綴“ab”是相等的鸭巴，所以就j就由6變成了3眷细；
因此得出規(guī)律：j值的多少取決于當前字符之前的串前后綴相似度；
KMP匹配算法中——next數(shù)組值推導(dǎo)
情況1:模式串中無任何字符重復(fù)
在例1的情況下鹃祖，模式串T中不存在任何重復(fù)的字符溪椎，所以此時next數(shù)組，推演過程符合公式中第1種情況與第3種情況恬口，因此next數(shù)組為={011111};
情況2:模式串類似于“abcabx”
當j=1校读，屬于情況1，則next [1]=0;
當j=2楷兽，3地熄，4時，屬于情況3芯杀，則next[2...4]={0111};
當j=5時端考，1到j(luò)-1范圍內(nèi)只有字符“abca”，顯然前綴a和后綴a想等揭厚，屬于其他情況next[5]=2
因為當主串匹配到第五個元素b的時候却特，說明b的前面也就是第四位的元素一定是a，不然肯定不會匹配到第五個元素筛圆，所以假設(shè)當?shù)谖鍌€元素不匹配的時候裂明，模式串可以從第二個元素開始與主串的第五個元素進行重新匹配
當j=6，1到j(luò)-1范圍內(nèi)只有字符“abcab”太援，顯然前綴ab和后綴ab想等闽晦，屬于其他情況next[6]=3
因為當主串匹配到第六個元素x的時候，說明x的前面也就是第四位和第五位的元素一定是ab提岔，不然肯定不會匹配到第六個元素仙蛉，所以假設(shè)當?shù)诹鶄€元素不匹配的時候，模式串可以從第三個元素開始與主串的第六個元素進行重新匹配碱蒙，因為主串的第四個和第五個元素一定和模式串的第一個和第二個元素相等
如果前后綴一個字符相等荠瘪，K值時2夯巷；兩個字符相等是3；n個相等K值就是n+1
情況3:模式串類似于“ababaaaba”
根據(jù)之前總結(jié)的K的求取規(guī)則哀墓，可以根據(jù)相等的字符換算出K值趁餐；
同時需要注意：
1.next數(shù)組是比較連續(xù)的前綴字符和后綴字符；例如當j=6時篮绰，字符串“ababa”最大前綴是“aba”后雷，后綴是“aba”
2.當j=7時，字符串“ababaa”阶牍，此時前綴是“a”喷面，后綴是“a”。不要誤以為是“ab”
情況4:模式串類似于“aaaaaaaab”
需要注意剛剛發(fā)生的重疊情況
KMP模式匹配算法實現(xiàn)
計算子串T的next數(shù)組:求解next數(shù)組其實就是在求解字符串的回溯位置;
KMP next數(shù)組的回溯位置求解過程模擬
? 假設(shè), 主串S = “abcababca” ; 模式串 T = “abcdex”
? 根據(jù)剛剛的公式的推演過程,我們其實非常情況next數(shù)組的應(yīng)該是 011111 . 但是我們?nèi)绾卫么a來求解出next數(shù)組了?
? 011111,意味著什么.
? 意味著其實模式串中abcdex 根本沒有可以便于回溯的地址.也就是當主串與模式串不匹配時,都需要從第1的位置上重新比較;
? 比如 abcababca 比較 abcdex 當比較到第4個位置是發(fā)現(xiàn)不匹配. 而此時主串的索引不變;
? 模式串的索引j當時等于4. 而此時發(fā)現(xiàn)不匹配,則要進行回溯. 那么應(yīng)該回溯到哪里了?
? j = next[j] ; j = 1; 也就是把abcbabca 的第4個字符與模式串的第1個字符串重新開始比較;
? 首先默認next[1] = 0; 表示它需要從0開始遍歷;
? 接下來設(shè)計2個索引下標 i = 0, j = 1;
? i 用于求解回溯的地址, 而j用于模式串的遍歷
? 如果出現(xiàn) i = 0,就是表示此時在模式串中并沒有出現(xiàn)它相同的字符, 需要記錄此時的回溯地址地址為1; next[j] = 1; 表示需要把? 從模式串的第一個字符開始比較;
? 如果T[i] == T[j] 表示此時已經(jīng)出現(xiàn)了模式串中有重疊字符,則回溯地址next[j] = i;
? 如果既沒有出現(xiàn) i = 0,且 T[i] == T[j] 表示此時從[i,j]這個范圍沒有出現(xiàn)回溯位置的調(diào)整,我們則把 i 回溯到next[i] 的位置;
? 此時在 i = 0,且j = 1的情況下.也是就是我們要找到[0,1]這個范圍的字符 a 是否存儲需要回溯的情況.
? 而這是只有字母 a,并且當前 i = 0, 所以如果主串和模式串匹配是,遇到第2個字符就不相配. 那么就應(yīng)該講主串后移1位,并且與模式串重新的第1位開始重新匹配計算;
? 但是此時i=0,j = 1; 所以我們應(yīng)該i++,j++;
? 并且將next[j] = i; 所以此時`next[2] = 1;
? 表示,當j=2時,發(fā)現(xiàn)字符不匹配.需要把控制模式串比較的下標索引回溯到1. 從第一個字符重新開始比較;
? 此時i = 1,j = 2; 明白此時在[0,2]范圍內(nèi),沒有可以回溯的合理位置;
? 所以將i回退到next[1]. 也就是 i = next[I];
? 那么如果i = 1,next[1] = 0;也就是0的位置; 0就意味著我們需要下一個字符進行比較時,我們需要頭開始比較;
? 那么如果是 next[i] 等于其他位置,表示把i回溯到其他位置. 而只有i有可回溯的可能性才會回溯到其他位置.
? 此時由于 i = 0, 那么就意味著如果需要從頭開始比較;
? 那么頭的位置指的是 1. 所以i++,j++; 因為這是當j = 3時, 如果不匹配需要回溯到開始的位置. 所以j 也是要?? 的;
? 同時next[j] = i; next[3] = 1;
圖形
? 這個過程我們通過圖例來分析! 這是KMP算法.也是眾多匹配算法中最為難以理解的算法
在求解next數(shù)組的4種情況:
默認next[1] = 0;
當 i=0時,表示當前的比應(yīng)該從頭開始.則i++,j++,next[j] = i;
當 T[i] == T[j] 表示2個字符相等,則i++,j++.同時next[j] = I;
當 T[i] != T[j] 表示不相等,則需要將i 退回到合理的位置. 則 i = next[i];
KMP算法之next數(shù)組求解
//----KMP 模式匹配算法---
//1.通過計算返回子串T的next數(shù)組;
//注意字符串T[0]中是存儲的字符串長度; 真正的字符內(nèi)容從T[1]開始;
void get_next(String T,int *next){
int i,j;
j = 1;
i = 0;
next[1] = 0;
//abcdex
//遍歷T模式串, 此時T[0]為模式串T的長度;
printf("length = %d\n",T[0]);
while (j < T[0]) {
printf("i = %d j = %d\n",i,j);
if(i ==0 || T[i] == T[j]){
//T[i] 表示后綴的單個字符;
//T[j] 表示前綴的單個字符;
++I;
++j;
next[j] = I;
printf("next[%d]=%d\n",j,next[j]);
}else
{
//如果字符不相同,則i值回溯;
i = next[I];
}
}
}
KMP查找算法
int count = 0;
//KMP 匹配算法
//返回子串T在主串S中第pos個字符之后的位置, 如不存在則返回0;
int Index_KMP(String S,String T,int pos){
//i 是主串當前位置的下標準,j是模式串當前位置的下標準
int i = pos;
int j = 1;
//定義一個空的next數(shù)組;
int next[MAXSIZE];
//對T串進行分析,得到next數(shù)組;
get_next(T, next);
count = 0;
//注意: T[0] 和 S[0] 存儲的是字符串T與字符串S的長度;
//若i小于S長度并且j小于T的長度是循環(huán)繼續(xù);
while (i <= S[0] && j <= T[0]) {
//如果兩字母相等則繼續(xù),并且j++,i++
if(j == 0 || S[i] == T[j]){
I++;
j++;
}else{
//如果不匹配時,j回退到合適的位置,i值不變;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return 0;
}
}
KMP匹配算法優(yōu)化
KMP 算法也是有缺陷的. 比如,如果我們的主串 [圖片上傳失敗...(image-20f255-1589979826881)]
,模式串 [圖片上傳失敗...(image-31fa91-1589979826881)]
. 其中 next 數(shù)組就是 [圖片上傳失敗...(image-1c516f-1589979826881)]
;
? 當開始匹配時, 當 i = 5, j = 5 時, 我們發(fā)現(xiàn)字符 "b" 與 字符 "a" 不相等時, 如圖① . 因此 j = next[5] = 4.
? 那么此時就如圖②. 此時字符 "b" 與 第4個位置上的 "a" 依然不等; j = next[4] = 3; 如圖③
? 以此內(nèi)推. 如圖④⑤; 當 j = next[1] = 0時,根據(jù)算法,此時 i++,j++; 得到i = 6,j = 1. 如圖⑥;
其實,在比較的過程發(fā)現(xiàn) 當中②③④⑤步驟的回溯比較都是多余的判斷;
由于 T 串的第二,三,四,五位置的字符都與首位 "a" 相等, 那么可以用 首位 next[1] 的值去取代與它相等的字符后續(xù)的 next[j] 值. 那么我們來對 next 函數(shù)來進行改良;
next 數(shù)組= {0,1,2,3,4,5}
如果要節(jié)省剛剛 ②③④⑤ 的無效比較則 需要next 數(shù)組={0,0,0,0,0,5}
KMP 模式匹配next 數(shù)組的優(yōu)化
? 當 j = 1,nextVal = 0; 繼續(xù)保持next[1]的邏輯;
? 當 j = 2時, 也就是當j = 2發(fā)生匹配錯誤, 那么由于第二個字符'b'的 next 值是1, 而且第一個字符是'a' .兩者不相等.所以nextval[2] = next[2] = 1;
? 當 j = 3 時, 此時因為第 3 個字符 'a' 的 next 值是1, 所以得知 第1位的'a' 與 第3位的'a' 是相等,則此時nextVal[3] = nextVal[1] = 0;
? 當j = 4 時, 因為第 4 個字符 "b" 的next = 2; 所以可以得知 它與第 2 位字符 "b" 是相等,則nextVal[4] = nextVal[2] = 1;
KMP_NextVal 數(shù)組邏輯
在求解nextVal數(shù)組的5種情況:
- 默認nextval[1] = 0;
- T[i] == T[j] 且++i,++j 后 T[i] 依舊等于 T[j] 則 nextval[i] = nextval[j]
- i = 0, 表示從頭開始i++,j++后,且T[i] != T[j] 則nextVal = j;
- T[i] == T[j] 且++i,++j 后 T[i] != T[j] ,則nextVal = j;
- 當 T[i] != T[j] 表示不相等,則需要將i 退回到合理的位置. 則 i = next[i];
代碼實現(xiàn)KMP_NextVal數(shù)組
void get_nextVal(String T,int *nextVal){
int i,j;
i = 1;
j = 0;
nextVal[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
++j;
++I;
//如果當前字符與前綴不同,則當前的j為nextVal 在i的位置的值
if(T[i] != T[j])
nextVal[i] = j;
else
//如果當前字符與前綴相同,則將前綴的nextVal 值賦值給nextVal 在i的位置
nextVal[i] = nextVal[j];
}else{
j = nextVal[j];
}
}
}
