字符串匹配算法是在實際工程中經(jīng)常遇到的問題，也是各大公司筆試面試的?？碱}目，本文主要介紹BF算法（最好想到的算法，也最好實現(xiàn)）和KMP算法（最經(jīng)典的）
一、BF算法
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是將目標(biāo)S的第一個字符與模式串T的第一個字符進行匹配，若相等，則繼續(xù)比較S的第二個字符和T的第二個字符，若不相等，則比較S的第二個字符和T的第一個字符，依次比較下去，直到得出最后的匹配結(jié)果。BF算法是一種蠻力法。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???---這段話來自百度百科
這段話晦澀難懂，需要例子支持。
下面我們就通過例子來解釋這個問題。 l假定我們給出字符串“ababcabccabcacbab”作為主串，然后給出子串:“abcac”現(xiàn)在我們需要查找子串是否在主串中出現(xiàn)，出現(xiàn)返回主串中的第一個匹配的下標(biāo)，失敗返回-1;
1.圖解：
2.代碼實現(xiàn)：?
思路：
分別用 i 和 j 來遍歷 主串 和 子串 ；
當(dāng)主串和子串字符相同 i++ ，j++ ；
不同時 i = i - j +1 （i從下一個i開始繼續(xù)遍歷） j = 0（子串回到開頭）；
直到 j >= lenSub (子串遍歷完了） 返回 i - j （主串中開始匹配的其實位置）
在Java中str == null和str.length == 0的區(qū)別：
str == null表示 str 沒有指向任何對象，就是沒有對應(yīng)堆中對象
str.length() == 0表示 str 指向一個字符串對象，但是這個字符串長度為0
//str代表主串 sub代表子串
public static int BF(String str, String sub) {
if (str == null || sub == null) {
return -1;
}
int lenStr = str.length();
int lenSub = sub.length();
if (lenStr == 0 || lenSub == 0) {
return -1;
}
int i = 0;//遍歷主串
int j = 0;//遍歷子串
while (i < lenStr && j < lenSub) {
if (str.charAt(i) == sub.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
//子串遍歷完了
if (j >= lenSub) {
return i - j;
}
return -1;
}二、KMP算法
KMP算法是一種改進的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特莫里斯一普拉特操作(簡稱KMP算法) 。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的。具體實現(xiàn)就是通過一個next( )函數(shù)實現(xiàn)，函數(shù)本身包含了模式串的局部匹配信息。KMP算法的時間復(fù)雜度O(m+n)?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ---這段話來自百度百科
?1. KMP算法解決的問題
對某些情況下的BF算法進行優(yōu)化
BF算法每次字符串匹配失敗，子串的 j 都會回到子串的第一個字符，但是我們看下面這個圖會發(fā)現(xiàn)在有些情況下這樣的回退是沒必要的：
當(dāng) i 和 j 都匹配到下標(biāo)為5的字符時，發(fā)現(xiàn)主串和字串的字符不匹配，BF算法在此時就會將i 回退到主串下標(biāo)1字符b，j回退到子串0下標(biāo)重新進行匹配，既然是匹配到最后一個字符才失敗，那么 i 前面和 j 前面一定有一部分是相同的，這里相同部分就是主串0，1和3，4下標(biāo)都是ab字符串，我們發(fā)現(xiàn)此時?j 回退到2下標(biāo)c位置重新開始合適，i 直接不回退
區(qū)別: KMP 和 BF 唯一不一樣的地方在,我主串的 i 并不會回退，并且 j 也不會移動到 0 號位置，而是回退到一個特殊的位置
2.圖解演示：
3. 為什么主串 i 不回退??
在下面這種情況下，在下標(biāo)2位置匹配失敗，i 即使回退到1位置也是沒有必要的，因為 i回退到1位置的字符b? 和 子串下標(biāo)0位置的字符a? 也不一樣
4.?j 的怎么進行位置的回退——引出next數(shù)組
從上面KMP算法解決的問題可知：
此時匹配失敗，我們不回退 i ，因為在這個地方匹配失敗，說明 i 的前面和 j 的前面，是有部分是相同的，不然兩個下標(biāo)不可能走到這里來，所以 j 回退到2下標(biāo)，i 不回退，這就是最好的情況
那么我們怎么知道 j 回退到哪個位置呢？由此引入了next數(shù)組
KMP 的精髓就是 next 數(shù)組: 這個數(shù)組用來保存某個位置匹配失敗后，回退的位置
也就是用 next[ i ]?= k來表示，不同的 i 來對應(yīng)一個k值， 這個 k 就是你將來要移動的i要移動的位置
就拿上面的例子來說，j 回退到2下標(biāo) 那么next數(shù)組中 next [ 5 ] = 2
而 K 的值是這樣求的（求next數(shù)組）:(1) 規(guī)則: 在子串中找到匹配成功部分的兩個相等的真子串(不包含本身)，一個以下標(biāo) 0 開始，另一個以-1 下標(biāo)結(jié)尾。
(2) 不管什么數(shù)據(jù) next[0]= -1;next1]= 0;在這里，我們以下標(biāo)來開始，而說到的第幾個第幾個是從 1 開始（也有些地方next[0]= 0;next1]= 1）同樣以上面的子串 abcabc 為例，求他的next數(shù)組：
下標(biāo)0和下標(biāo)1是固定的，那就不用說
下標(biāo)2?：j 處于下標(biāo)2?，我們就看有沒有一個字符串 以下標(biāo)0（a字符）開始 ，另一個字符串以下標(biāo) -1（b字符）結(jié)束 的兩個相同的字符串 ab這三個字符中肯定沒有 所以next [2] = 0
下標(biāo)3：j 處于下標(biāo)3?，我們就看有沒有一個字符串 以下標(biāo)0（a字符）開始 ，另一個字符串以下標(biāo) -1（c字符）結(jié)束 的兩個相同的字符串 abc這三個字符中肯定沒有 所以next [3] = 0
下標(biāo)4：j處于下標(biāo)4，我們同樣看?有沒有一個字符串 以下標(biāo)0（a字符）開始 ，另一個字符串以下標(biāo) -1（a字符）結(jié)束 的兩個相同的字符串 abca這三個字符中是有相同字符串a(chǎn)的?所以next [4] = 1（這里的1代表相同字符串的長度,沒有就為0）
下標(biāo)5?：j處于下標(biāo)5?abcab 中ab 為相同的(一個a開頭 另一個b結(jié)尾)字符串 所以next [5] = 2
求next數(shù)組的練習(xí): 跟上面的過程一樣，如果不懂可以去看 博哥視頻講解的KMP算法 30min的位置
練習(xí) 1: 舉例對于”ababcabcdabcde”，求其的 next 數(shù)組?
答案：? ? ? ? ? ? ? ? ?-10012012001200
練習(xí) 2: 再對”abcabcabcabcdabcde”,求其的 next 數(shù)組?
答案：? ? ? ? ?-10001 2345678901230
一般情況答案都是next[0]= 0;next1]= 1，所以我們在此答案基礎(chǔ)上全部+1即可
從上面的答案我們可以得出結(jié)論：數(shù)組在增的時候都是一個一個+1，不可能跳著加
到這里大家對如何求next數(shù)組應(yīng)該問題不大了，接下來的問題就是 :
5.已知next[ i ]?= k;怎么求next[i+1]=??
如果我們能夠通過 next [ i ]的值,通過一系列轉(zhuǎn)換得到 next?[ i+1]得值，那么我們就能夠?qū)崿F(xiàn)這部分
首先假設(shè): next[ i ]?= k 成立 (為了方便數(shù)組名命名為p）
那么，就有這個式子成立:p [ 0 ]...p [ k-1 ] = p [ x?] ..p [ i-1 ]
因為 i -1 -k = k -1 那么 x = i - k ，也就是p [ 0 ]...p [ k-1 ] = p [ i - k?] ..p [ i-1 ]
到這一步: 我們再假設(shè)如果 p [ k ]?= p [ i ] ;在上面得到的式子兩邊加上這個式子
我們可以得到p [ 0 ]...p [ k?] = p [ i-k?] ..p [ i?] ;那這個就是 next[ i+1]= k+1;
那么: p[ i ]?!= p[ k ]?呢?
看如下實例:
一次不匹配 ，j 回退到 2下標(biāo)位置 不一定是你要找的?
繼續(xù)回退 此時回退到了0下標(biāo) （也就是說 k一直回退 去找 p [i] == p [k] ,這樣就滿足了p [ k ]?= p [ i ])
6.KMP算法代碼實現(xiàn)
//找到子串在主串當(dāng)中的下標(biāo)
public static int KMP(String str,String sub,int pos) {
if(str == null||sub == null) return -1;
int lenStr = str.length();
int lenSub = sub.length();
if(lenStr == 0||lenSub == 0) return -1;
if(pos<0 || pos >= lenStr) return -1;
int [] next = new int[lenSub];
getNext(sub,next);
int i = pos;//從pos位置開始遍歷主串
int j = 0;//遍歷子串
while(i < lenStr && j <lenSub) {
//這里要考慮到一開始就不匹配，j=-1
if (j==-1||str.charAt(i) == sub.charAt(j)) {
i++;
j++;
} else {
//下標(biāo)不一樣，一直回退
j = next[j];
}
}
if(j==lenSub) {
return i-j;
}
return -1;
}
//重點：求子串的next數(shù)組
public static void getNext(String sub,int [] next) {
next[0] = -1;
next[1] = 0;
int i = 2;//i表示所求next數(shù)組的下標(biāo)，是提前走了一步的
int k = 0;//比較是否相等的前一項的k
//這里next[i]就是要求的，和我們分析的next[i+1]一樣
// 原來判斷的是p[i]==p[k]，現(xiàn)在應(yīng)該判斷p[i-1]==p[k]
while(i < sub.length()) {
//此處要考慮k回退到了-1位置，next值就為0
if (k==-1||sub.charAt(i-1) ==sub.charAt(k)) {
next[i] = k+1;
k++;
i++;
} else {
//p[i-1]！=p[k]，則k繼續(xù)回退
k = next[k];
}
}
}7.next數(shù)組的優(yōu)化
為什么要對next數(shù)組進行優(yōu)化？
有如下串:aaaaaaaab,他的 next 數(shù)組是-1,0,1,2,3,4,5,6,7
假設(shè)5位置匹配失敗，那么就得回退到4位置，4位置和5位置都是a，那么還得回退到3位置，而3位置和4位置都是a，還得繼續(xù)回退，就這樣一直回退到0位置，由此引入了nextval數(shù)組進行了優(yōu)化
next 數(shù)組的優(yōu)化，即如何得到 nextval?數(shù)組:
（1）回退到的位置和當(dāng)前字符一樣，就寫回退那個位置的nextval值
（2）如果回退到的位置和當(dāng)前字符不一樣，就寫當(dāng)前字符原來的next值
就以上面字符串為例：
0下標(biāo)：肯定還是為-1
1下標(biāo)：這個位置回退到0位置，因為這個位置的值和0位置（回退的位置）的值一樣，所以這個位置的值就寫回退位置的值（即-1）
2-7下標(biāo)：這些位置回退到前一個位置，值都是一樣的，所以都是-1
8下標(biāo):? 回退到的位置和當(dāng)前字符不一樣，直接寫next[ 8 ]的值7即可
則修正后的數(shù)組 nextval?是:-1， -1，-1，-1， -1， -1， -1， -1，7。
練習(xí): 模式串 t='abgabbcabcaabdab’，該模式串的 next 數(shù)組的值為 ( D )nextva1 數(shù)組的值為 (F)
答案：在下面答案的基礎(chǔ)上+1即可選擇
??這里也不做過多的解釋，過程跟上面一樣，不懂的可以評論區(qū)或者私信問我，或者 看博哥視頻講解的KMP算法 2h的位置
本次內(nèi)容就到此啦，歡迎評論區(qū)或者私信交流，覺得筆者寫的還可以，或者自己有些許收獲的，麻煩鐵汁們動動小手，給俺來個一鍵三連，萬分感謝 !文章來源：http://www.zghlxwxcb.cn/news/detail-766328.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-766328.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】字符串匹配|BF算法|KMP算法|next數(shù)組的優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
