引言

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

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

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

暴力 Vs KMP

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

KMP：失配，字串向后n位，成功匹配數(shù)m位。n，m的計算即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

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

index	0	1	2	3	4	5	6	7
pattern[index]	a	b	c	d	a	b	c	y
same[index]	-1	0	0	0	0	1	2	3
move[index]	1	1	2	3	4	4	4	4

部分匹配表（失配函數(shù)）

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

（難點）部分匹配表的構造

以 aabaabaaa為例子，構造部分匹配表

index	0	1	2	3	4	5	6	7	8
pattern[index]	a	a	b	a	a	b	a	a	a
same[index]	-1	0	1	0	1	2	3	4	5
move[index]	1	1	1	3	3	3	3	3	3

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

• 如果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]的大小關系，無法得出結果則繼續(xù)回溯。
  • 如果回溯到初始情況因為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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

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

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

廣告

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