您好,登錄后才能下訂單哦!
這篇文章主要講解了“Java數(shù)據(jù)結(jié)構(gòu)之KMP算法怎么實(shí)現(xiàn)”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“Java數(shù)據(jù)結(jié)構(gòu)之KMP算法怎么實(shí)現(xiàn)”吧!
這是最常見(jiàn)的算法字符串匹配算法,暴力匹配也叫樸素匹配。
思路很簡(jiǎn)單,從主串的第i個(gè)字符開(kāi)始遍歷,依次與子串的每個(gè)字符進(jìn)行匹配,如果某個(gè)字符匹配失敗,則主串回溯第i+1個(gè)字符,子串回溯到第1個(gè)字符,重新開(kāi)始匹配,直到遍歷完主串匹配失敗或者遍歷完子串匹配成功。
很明顯這種算法需要在一個(gè)雙重for循環(huán)中實(shí)現(xiàn),時(shí)間復(fù)雜度為O(m*n),m為主串長(zhǎng)度,n為子串長(zhǎng)度。隨著字符串長(zhǎng)度的增長(zhǎng),時(shí)間復(fù)雜度快速上升。
Java中字符串的contains方法實(shí)際上就是采用的BF算法。
public static int bf(String word, String k) { char[] wordChars = word.toCharArray(); char[] keyChars = k.toCharArray(); for (int i = 0; i < wordChars.length; i++) { int j = 0, x = i; //依次匹配 while (x < wordChars.length && j < keyChars.length && wordChars[x] == keyChars[j]) { x++; j++; } if (j == keyChars.length) { return i; } } return -1; }
KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 于1977年共同提出的,稱之為 Knuth-Morria-Pratt 算法,簡(jiǎn)稱 KMP 算法。
KMP算法是一種改進(jìn)的字符串匹配算法,核心是利用之前的匹配失敗時(shí)留下的信息,選擇最長(zhǎng)匹配長(zhǎng)度直接滑動(dòng),從而減少匹配次數(shù)。KMP 算法時(shí)間復(fù)雜度為O(m+n),m為主串長(zhǎng)度,n為子串長(zhǎng)度。
BF匹配失敗之后,主串和子串都會(huì)最大回溯,但是很多時(shí)候都是沒(méi)有必要的。例如對(duì)于主串a(chǎn)bababcd,子串a(chǎn)babc,第一次匹配之后,很明顯主串和子串會(huì)匹配失敗,但是我們能夠知道他們的能夠匹配的前綴串,即abab:
如果在第二次匹配的時(shí)候,主串不回溯,子串滑動(dòng)兩個(gè)字符長(zhǎng)度,那么我們就能在第二次的時(shí)候?qū)崿F(xiàn)匹配成功。
到這里,這種加速的方法已經(jīng)呼之欲出了,但是我們先介紹兩個(gè)重要概念:
1.匹配前綴:在某一次主串和子串的匹配失敗之后,前面匹配成功的那部分子串就被稱為匹配前綴。這就是一次匹配失敗時(shí)留下的信息。
例如主串a(chǎn)bcde,子串a(chǎn)bcc,那么在第一次匹配的時(shí)候,匹配前綴為abc。
2.最長(zhǎng)匹配長(zhǎng)度:對(duì)于每次匹配失敗后的匹配前綴串,其前綴子串(連續(xù),且一定包括第一個(gè)字符,不包括最后一個(gè)字符)和后綴子串(連續(xù),且一定包括最后一個(gè)字符,不包括第一個(gè)字符)中,相同的前后綴子串的最長(zhǎng)子串長(zhǎng)度,此時(shí)的前綴、后綴字串也被稱為最長(zhǎng)真前綴、后綴子串。
例如匹配前綴abc,沒(méi)有匹配的前綴和后綴,那么其最長(zhǎng)匹配長(zhǎng)度為0。
例如匹配前綴cbcbc,最長(zhǎng)匹配的前綴和后綴子串為cbc,那么其最長(zhǎng)匹配長(zhǎng)度為3。
例如匹配前綴abbcbab,最長(zhǎng)匹配的前綴和后綴子串為ab,那么其最長(zhǎng)匹配長(zhǎng)度為2。
有了這兩個(gè)概念,那么我們才能進(jìn)行跳躍式滑動(dòng),對(duì)于主串,在匹配失敗的位置不進(jìn)行回溯,對(duì)于子串,則是回溯(滑動(dòng))到其匹配前綴的最長(zhǎng)匹配長(zhǎng)度的位置上繼續(xù)匹配,這樣就跳過(guò)了之前的部字符串的匹配,且只需要匹配剩下的部分字符串即可。
我們?cè)僭敿?xì)解釋下,這里子串跳過(guò)的到底什么?實(shí)際上它跳過(guò)的就是匹配前綴串的最長(zhǎng)匹配長(zhǎng)度串。
設(shè)主串a(chǎn)bababcd,子串a(chǎn)babc,第一次匹配失敗之后,主串匹配索引i=4,子串匹配索引j=4,此時(shí)匹配的相同前綴串為abab,它的最長(zhǎng)匹配長(zhǎng)度為2,即最長(zhǎng)前綴串a(chǎn)b和最長(zhǎng)后綴串a(chǎn)b。
那么第二次匹配之前,字串匹配索引j直接跳到第一匹配的相同前綴串的最長(zhǎng)匹配長(zhǎng)度的索引位置上即j=2。我們可以這么理解,主串的第一次匹配的相同前綴串的最長(zhǎng)匹配后綴,與子串第一次匹配的相同前綴串的最長(zhǎng)匹配前綴相等(或者說(shuō)重合)。這是我們?cè)诘讓右淮问∑ヅ渲蟮玫降挠行畔ⅲ诘诙纹ヅ鋾r(shí)自然可以利用起來(lái),利用最長(zhǎng)的前后綴匹配信息,跳過(guò)這些多余的匹配,實(shí)現(xiàn)加速。(后續(xù)學(xué)習(xí)的AC自動(dòng)機(jī)也是采用了前后綴匹配的思想)
這就是KMP算法加速的核心原理,每次匹配失敗之后,利用匹配失敗的信息,找到最長(zhǎng)匹配長(zhǎng)度,然后主串不回溯,子串盡可能少的回溯,相比于BF算法,減少了沒(méi)必要的匹配次數(shù)。
基于上面的原理,我們知道可能會(huì)不止一次查找最長(zhǎng)匹配長(zhǎng)度,而且我們會(huì)發(fā)現(xiàn),最長(zhǎng)匹配長(zhǎng)度的范圍只能在子串長(zhǎng)度范圍之內(nèi),而且其計(jì)算結(jié)果只和子串有關(guān)。那么我們就可以先初始化一個(gè)數(shù)組,用來(lái)保存不同長(zhǎng)度的前綴的最長(zhǎng)匹配長(zhǎng)度。
這就是所謂的next數(shù)組,也被稱為部分匹配表(Partial Match Table),也是KMP算法的核心。next數(shù)組的大小就是子串的長(zhǎng)度,每個(gè)的索引位置i表示長(zhǎng)度為i+1的子串的匹配前綴子串,值v表示對(duì)應(yīng)匹配前綴子串的最長(zhǎng)匹配長(zhǎng)度。
假設(shè)子串為ababc,那么next數(shù)組值為:
假設(shè)子串為abcabdabcabc,那么對(duì)應(yīng)的next數(shù)組如下:
其實(shí)很好理解:
子串匹配前綴串 | 最長(zhǎng)匹配長(zhǎng)度 |
---|---|
a | 0 |
ab | 0 |
abc | 0 |
abca | 1 |
abcab | 2 |
abcabd | 0 |
abcabda | 1 |
abcabdab | 2 |
abcabdabc | 3 |
abcabdabca | 4 |
abcabdabcab | 5 |
abcabdabcabc | 3 |
現(xiàn)在,我們的首要問(wèn)題變成了求next數(shù)組。
首先,切next數(shù)組的問(wèn)題實(shí)際上就是求最大的前、后綴長(zhǎng)度的問(wèn)題,那么我們可以使用最樸素的方式求解:
public static int[] getNext(String word) { int[] next = new int[word.length()]; //從兩個(gè)字符的子串開(kāi)始遍歷 for (int i = 1; i < word.length(); i++) { int k = i; //從最大的最長(zhǎng)匹配值開(kāi)始縮短 while (k > 0) { //如果前綴等于后綴,那么表示獲取到了最長(zhǎng)匹配,直接返回 if (word.substring(0, k).equals(word.substring(i - (k - 1), i + 1))) { next[i] = k; break; } k--; } } return next; }
不難發(fā)現(xiàn),求解next數(shù)組的時(shí)間復(fù)雜度為O(n^2),是否有更快速的方法呢?當(dāng)然有,可以發(fā)現(xiàn),在求next[i]的最長(zhǎng)匹配長(zhǎng)度的時(shí)候,next[0], next[1], … next[i-1]的結(jié)果已經(jīng)求出來(lái)了。因此我們嘗試?yán)么饲暗慕Y(jié)果直接推導(dǎo)出后面的結(jié)果。下面是分情況討論。
設(shè)子串為str=ababc,i=3,那么next[i-1]=1,即子串a(chǎn)ba的的最長(zhǎng)匹配長(zhǎng)度為1,那么str[next[i-1]]實(shí)際上就是最長(zhǎng)匹配子串前綴后一個(gè)字符,即str[1]=b。
如果str[i]=str[next[i-1]],就相當(dāng)于在前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度的基礎(chǔ)上增加了一位,即next[i]=next[i-1]+1。如下圖:
如果str[i]!=str[next[i-1]],此時(shí)就會(huì)復(fù)雜一些。此時(shí)我們需要縮短最長(zhǎng)匹配子串的長(zhǎng)度,具體怎么縮短呢?
設(shè)str = abcabdabcabc,設(shè)i = 11,即最后一個(gè)字符c,那么next[i-1] = 5,但是由于str[i] != str[next[i-1]],即d != c,那么此時(shí)我們需要求i-1的最長(zhǎng)匹配長(zhǎng)度子串a(chǎn)bcab的最長(zhǎng)匹配長(zhǎng)度子串,即next[next[i-1]-1] = 2,然后判斷str[i]是否等于str[next[next[i-1]-1]],如果相等則同第一種情況,否則繼續(xù)縮減直到next[next[i-1]-1]為0為止,此時(shí)表示當(dāng)前子串的最長(zhǎng)匹配長(zhǎng)度也為0。如下圖:
基于上面的規(guī)律,我們的改進(jìn)算法如下:
public static int[] getNext2(String k) { int[] next = new int[k.length()]; char[] chars = k.toCharArray(); //i表示匹配的字符索引,pre表示前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度,即next[i-1] int i = 1, pre = next[i - 1]; while (i < k.length()) { //如果新增的字符與前一個(gè)子串的最長(zhǎng)匹配子串前綴的后一個(gè)字符相等 if (chars[i] == chars[pre]) { //next[i]=next[i-1]+1 pre++; next[i] = pre; //繼續(xù)后移 i++; } //如果不相等,且前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度不為0 //那么求i-1的最長(zhǎng)匹配長(zhǎng)度子串的最長(zhǎng)匹配長(zhǎng)度子串,即pre=next[next[i-1]-1] //然后在下一輪循環(huán)中繼續(xù)比較chars[i] == chars[pre],此時(shí)i并沒(méi)有自增 else if (pre != 0) { //next[next[i-1]-1] pre = next[pre - 1]; } //如果不相等,且前一個(gè)子串的最長(zhǎng)匹配長(zhǎng)度為0,那么說(shuō)明當(dāng)前子串的最長(zhǎng)匹配長(zhǎng)度也為0 else { //當(dāng)前子串的最長(zhǎng)匹配長(zhǎng)度為0 next[i] = 0; //繼續(xù)后移 i++; } } return next;
這種算法的時(shí)間復(fù)雜度為O(n),大大縮短了求next數(shù)組的時(shí)間。
有了next數(shù)組,那么KMP算法就很容易實(shí)現(xiàn)了。
使用i和j分別表示主串和子串的匹配進(jìn)度,i永遠(yuǎn)不會(huì)回退,依次匹配主串和子串的字符:
1.如果字符相等則推進(jìn)i、j,并且判斷如果匹配到了一個(gè)完整的子串,那么返回起始索引。
2.如果不相等:
如果當(dāng)前子串進(jìn)度為0,那么子串不需要回退,主串向后推進(jìn)i,重新開(kāi)始匹配;
如果當(dāng)前子串進(jìn)度不為0,那么子串進(jìn)度需要回退到next[j-1]的位置,此前的位置不再需要匹配,主串不需要向后推進(jìn)i,隨后重新開(kāi)始匹配。
如果i進(jìn)度匹配完畢,那么退出循環(huán),表示沒(méi)有匹配到任何完整的子串,返回-1。
public static int kmp(String word, String k) { int[] next = getNext(k); //i,j分別表示主串和子串的匹配進(jìn)度 int m = word.length(), n = k.length(), i = 0, j = 0; //如果i匹配完畢,那么退出循環(huán) while (i < m) { //如果字符相等,那么向后推進(jìn)i、j if (word.charAt(i) == k.charAt(j)) { i++; j++; //如果匹配到了一個(gè)完整的子串 if (j == n) { //返回起始索引 return i - n; } } //如果當(dāng)前子串進(jìn)度為0,那么子串不需要回退,主串向后推進(jìn)i else if (j == 0) { i++; } //如果當(dāng)前子串進(jìn)度不為0,那么子串需要回退,主串不需要向后推進(jìn)i else { //子串進(jìn)度j回退 j = next[j - 1]; } } return -1; }
上面我們的實(shí)現(xiàn)是返回第一個(gè)匹配到的模式串的起始索引,那么如果我們需要返回所有匹配到的模式串的起始索引呢?
其實(shí)也很簡(jiǎn)單。在每次匹配某個(gè)字符成功之后判斷,如果匹配到了一個(gè)完整的子串,那么我們求起始索引并且加入結(jié)果集,然后子串點(diǎn)位j需要回退,繼續(xù)循環(huán)。
public static List<Integer> kmpAll(String word, String k) { List<Integer> res = new ArrayList<>(); int[] next = getNext(k); //i,j分別表示主串和子串的匹配進(jìn)度 int m = word.length(), n = k.length(), i = 0, j = 0; //如果i匹配完畢,或者j匹配完畢,那么退出循環(huán) while (i < m) { //如果字符相等,那么向后推進(jìn)i、j if (word.charAt(i) == k.charAt(j)) { i++; j++; //如果匹配到了一個(gè)完整的子串 if (j == n) { //將起始索引加入結(jié)果集 res.add(i - n); //子串進(jìn)度j回退 j = next[j - 1]; } } //如果當(dāng)前子串進(jìn)度為0,那么子串不需要回退,主串向后推進(jìn)i else if (j == 0) { i++; } //如果當(dāng)前子串進(jìn)度不為0,那么子串需要回退,主串不需要向后推進(jìn)i else { //子串進(jìn)度j回退 j = next[j - 1]; } } return res; }
感謝各位的閱讀,以上就是“Java數(shù)據(jù)結(jié)構(gòu)之KMP算法怎么實(shí)現(xiàn)”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)Java數(shù)據(jù)結(jié)構(gòu)之KMP算法怎么實(shí)現(xiàn)這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。