KMP字符串匹配算法-創(chuàng)新互聯(lián)

引言

KMP算法的思想在于，讓每一次匹配都盡可能使用先前匹配產(chǎn)生的信息(部分匹配表)。

成都創(chuàng)新互聯(lián)秉承實(shí)現(xiàn)全網(wǎng)價(jià)值營銷的理念，以專業(yè)定制企業(yè)官網(wǎng)，成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、外貿(mào)網(wǎng)站建設(shè)，重慶小程序開發(fā)，網(wǎng)頁設(shè)計(jì)制作，手機(jī)網(wǎng)站開發(fā)，全網(wǎng)營銷推廣幫助傳統(tǒng)企業(yè)實(shí)現(xiàn)“互聯(lián)網(wǎng)+”轉(zhuǎn)型升級專業(yè)定制企業(yè)官網(wǎng),公司注重人才、技術(shù)和管理，匯聚了一批優(yōu)秀的互聯(lián)網(wǎng)技術(shù)人才,對客戶都以感恩的心態(tài)奉獻(xiàn)自己的專業(yè)和所長。

KMP算法的難點(diǎn)在于，部分匹配表的構(gòu)造也在盡可能使用之前構(gòu)造過程中的信息（動(dòng)態(tài)規(guī)劃？）。

暴力 Vs KMP

暴力：失配，字串向后1位，成功匹配字符數(shù)歸0。

KMP：失配，字串向后n位，成功匹配數(shù)m位。n，m的計(jì)算即KMP算法的核心。

找規(guī)律
??          ??
abcdabcy     abcdabcy

a?          a?
abcdabcy     abcdabcy

ab?         ab?
abcdabcy      abcdabcy

abc?        abc?
abcdabcy       abcdabcy

abcd?       abcd?
abcdabcy        abcdabcy

abcda       abcda?
abcdabcy        abcdabcy

abcdab?     abcdab?
abcdabcy        abcdabcy

abcdabc?    abcdabc?
abcdabcy        abcdabcy

abcdabcy
abcdabcy

觀察得知，移動(dòng)的位數(shù)分別需要考察 a ab abc abcd abcda abcdab abcdabc的前綴和后綴是否一樣。
same[index]可以理解為pattern[index]之前的前后綴匹配大長度
為了使得move[index] = index - same[index]，規(guī)定same[0] = -1

index01234567
pattern[index]abcdabcy
same[index]-10000123
move[index]11234444
部分匹配表（失配函數(shù)）

上一部分中最后的表格能極大的幫助我們完成字符串的匹配，它也就是所謂的部分匹配表。使用該表的時(shí)機(jī)即pattern[index]無法匹配，所以該表也稱失配函數(shù)

（難點(diǎn)）部分匹配表的構(gòu)造

以 aabaabaaa為例子，構(gòu)造部分匹配表

index012345678
pattern[index]aabaabaaa
same[index]-101012345
move[index]111333333

類似動(dòng)態(tài)規(guī)劃問題，如果我們已知same[index-1] = k，那么pattern[0...(index-2)]的前后綴匹配大長度已知，即pattern[0...k-1] == pattern[(index-k-1)...(index-2)]。
在求same[index]時(shí)我們需要考慮新的字符pattern[index - 1]，也就增加了1個(gè)后綴需要考慮的字符。

  • 如果pattern[k] == pattern[index-1]，那么pattern[0...k] == pattern[(index-k-1)...(index-1)]，那么same[index] = same[index - 1] + 1
  • 如果pattern[k] != pattern[index-1]，則需要回溯到更小的匹配長度，一定小于k。我們考慮same[k]的定義，即pattern[k]之前的前后綴大匹配長度，是能回溯到的最好的匹配長度。
    • 故繼續(xù)判斷pattern[same[k]]和pattern[index - 1]的大小關(guān)系，無法得出結(jié)果則繼續(xù)回溯。
    • 如果回溯到初始情況因?yàn)?code>same[0] == -1，則same[index] = 0
java代碼
public static int[] getSame(String modelString) {int[] same = new int[100];
    same[0] = -1;
    int i = 0;
    int j = same[i];
    while (i< modelString.length()) {if (j == -1 || modelString.charAt(i) == modelString.charAt(j)) {// same[i+1] = same[i] + 1
            i++;
            j++;
            same[i] = j;
        } else {// backtrack
            j = same[j];
        }
    }
    return same;
}
最后

same可能就是其他文章中提到的next數(shù)組

參考

KMP字符串匹配算法【雙語字幕】

wiki百科

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：KMP字符串匹配算法-創(chuàng)新互聯(lián)
文章路徑：http://muchs.cn/article16/dpojgg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、面包屑導(dǎo)航、搜索引擎優(yōu)化、網(wǎng)站改版、網(wǎng)站導(dǎo)航、網(wǎng)站營銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

外貿(mào)網(wǎng)站制作