title: 串的模式匹配算法之kmp
tags: 數(shù)據結構與算法之美
author: 辰砂tj
1.引言
首先我們需要了解串的模式算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）；常見的算法種類：
BF算法（又稱古典的吆视、經典的螺捐、樸素的远豺、窮舉的）收夸，KMP算法（特點：速度快）。網上有很多帖子验懊，博客寫的都特別好，這篇文章也是對自己的一個總結尸变。
2.BF算法
BF算法設計思想：
將主串的第pos個字符和模式的第一個字符比較 </br>
若相等义图，繼續(xù)逐個比較后續(xù)字符；</br>
若不等召烂，從主串的下一字符起碱工，重新與模式的第一個字符比較。 </br>
直到主串的一個連續(xù)子串字符序列與模式相等 奏夫。</br>
返回值為S中與T匹配的子序列第一個字符的序號怕篷，即匹配成功。</br>
否則酗昼，匹配失敗廊谓，返回值 0
1.舉例：
假設現(xiàn)在我們面臨這樣一個問題：有一個文本串S，和一個模式串P麻削，現(xiàn)在要查找P在S中的位置蒸痹，怎么查找呢？</p>
如果用暴力匹配的思路呛哟，并假設現(xiàn)在文本串S匹配到 i 位置叠荠，模式串P匹配到 j 位置，則有：
如果當前字符匹配成功（即S[i] == P[j]）扫责，則i++榛鼎，j++，繼續(xù)匹配下一個字符鳖孤；
如果失配（即S[i]! = P[j]）借帘，令i = i - (j - 1) （表示主串的位置回到當前的下一個位置），j = 0淌铐。相當于每次匹配失敗時，i 回溯蔫缸，j 被置為0腿准。
public static int bfMatch(char[] s, char[] p) {
int sLen = s.length;
int pLen = p.length;
int i = 0;
int j = 0;
while (i < sLen && j < pLen) {
if (s[i] == p[j]) {
//①如果當前字符匹配成功（即S[i] == P[j]），則i++，j++
i++;
j++;
} else {
//②如果失配（即S[i]! = P[j]）吐葱，令i = i - (j - 1)街望，j = 0
// i - (j - 1) 表示主串的位置回到當前的下一個位置。
i = i - j + 1;
j = 0;
}
}
//匹配成功弟跑，返回模式串p在文本串s中的位置灾前，否則返回-1
if (j == pLen) {
return i - j;
} else {
return -1;
}
}
public static void main(String[] args) {
String s = "BBC ABCDAB ABCDABCDABDE";
String p = "ABCDABD";
System.out.println(bfMatch(s.toCharArray(),p.toCharArray()));
}
2.時間復雜度說明：
若n為主串長度，m為子串長度孟辑，最壞情況是
主串前面n-m個位置都部分匹配到子串的最后一位哎甲，即這n-m位各比較了m次
最后m位也各比較了1次
總次數(shù)為：(n-m)m+m＝(n-m+1)m
若m<<n，則算法復雜度O(n*m)
網上有個很好的例子饲嗽，故引用：
舉個例子炭玫，如果給定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”貌虾，現(xiàn)在要拿模式串P去跟文本串S匹配吞加，整個過程如下所示：
1.S[0]為B，P[0]為A尽狠，不匹配衔憨，執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)袄膏，j = 0”践图，S[1]跟P[0]匹配，相當于模式串要往右移動一位（i=1哩陕，j=0）
2.S[1]跟P[0]還是不匹配平项，繼續(xù)執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)悍及，j = 0”闽瓢，S[2]跟P[0]匹配（i=2，j=0）心赶，從而模式串不斷的向右移動一位（不斷的執(zhí)行“令i = i - (j - 1)扣讼，j = 0”，i從2變到4缨叫，j一直為0）
3.直到S[4]跟P[0]匹配成功（i=4，j=0）耻姥，此時按照上面的暴力匹配算法的思路销钝，轉而執(zhí)行第①條指令：“如果當前字符匹配成功（即S[i] == P[j]），則i++琐簇，j++”蒸健，可得S[i]為S[5]座享，P[j]為P[1]，即接下來S[5]跟P[1]匹配（i=5似忧，j=1）
4.S[5]跟P[1]匹配成功渣叛，繼續(xù)執(zhí)行第①條指令：“如果當前字符匹配成功（即S[i] == P[j]），則i++盯捌，j++”淳衙，得到S[6]跟P[2]匹配（i=6，j=2）饺著，如此進行下去
5.直到S[10]為空格字符箫攀，P[6]為字符D（i=10，j=6）瓶籽，因為不匹配匠童，重新執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)塑顺，j = 0”汤求，相當于S[5]跟P[0]匹配（i=5，j=0）
6.至此严拒，我們可以看到扬绪，如果按照暴力匹配算法的思路，盡管之前文本串和模式串已經分別匹配到了S[9]裤唠、P[5]挤牛，但因為S[10]跟P[6]不匹配，所以文本串回溯到S[5]种蘸，模式串回溯到P[0]墓赴，從而讓S[5]跟P[0]匹配。
而S[5]肯定跟P[0]失配航瞭。為什么呢诫硕？因為在之前第4步匹配中，我們已經得知S[5] = P[1] = B刊侯，而P[0] = A章办，即P[1] != P[0]，故S[5]必定不等于P[0]滨彻，所以回溯過去必然會導致失配藕届。那有沒有一種算法，讓i 不往回退亭饵，只需要移動j 即可呢休偶？
3.KMP算法（主串指針不回溯）
算法思想：利用已經部分匹配的結果而加快模式串的滑動速度？且主串S的指針i不必回溯辜羊！可提速到O(n+m)椅贱！
算法步驟：
下面先直接給出KMP的算法流程：
假設現(xiàn)在文本串S匹配到 i 位置懂算，模式串P匹配到 j 位置 </p>
如果j = -1，或者當前字符匹配成功（即S[i] == P[j]）庇麦，都令i++番舆，j++聂儒，繼續(xù)匹配下一個字符虱黄； </p>
如果j != -1命满，且當前字符匹配失斣印（即S[i] != P[j]）戒祠，則令 i 不變瓢对，j = next[j]靠胜。此舉意味著失配時萌衬，模式串P相對于文本串S向右移動了j - next [j] 位饮醇。 </p>
換言之，當匹配失敗時秕豫，模式串向右移動的位數(shù)為：失配字符所在位置 - 失配字符對應的next 值（next 數(shù)組的求解會在下文的3.3.3節(jié)中詳細闡述）朴艰，即移動的實際位數(shù)為：j - next[j]，且此值大于等于1混移。 </p>
很快祠墅，你也會意識到next 數(shù)組各值的含義：代表當前字符之前的字符串中，有多大長度的相同前綴后綴歌径。例如如果next [j] = k毁嗦，代表j 之前的字符串中有最大長度為k 的相同前綴后綴。
此也意味著在某個字符失配時回铛，該字符對應的next 值會告訴你下一步匹配中狗准，模式串應該跳到哪個位置（跳到next [j] 的位置）。如果next [j] 等于0或-1茵肃，則跳到模式串的開頭字符腔长，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某個字符免姿，而不是跳到開頭饼酿，且具體跳過了k 個字符。
public static int kmpMatch(char[] s, char[] p) {
int sLen = s.length;
int pLen = p.length;
int i = 0;
int j = 0;
while (i < sLen && j < pLen) {
if (s[i] == p[j]) {
//①如果當前字符匹配成功（即S[i] == P[j]）胚膊，則i++故俐，j++
i++;
j++;
} else {
j = next[j];
}
}
//匹配成功，返回模式串p在文本串s中的位置紊婉，否則返回-1
if (j == pLen) {
return i - j;
} else {
return -1;
}
}
為此,定義next[j]函數(shù)药版，表明當模式中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置喻犁。
1.如何求next()?
1.尋找前綴后綴最長公共元素長度
比如 字符串 ‘a’ 的前綴就是為空槽片，后綴也是為空何缓，所以前綴后綴的意思，是不包括當前字符串还栓，字符串 ‘ab’ 的前綴是a碌廓，后綴是b。
定義： 對于P = p0 p1 ...pj-1 pj剩盒，尋找模式串P中長度最大且相等的前綴和后綴谷婆。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大長度為k+1的相同前綴后綴辽聊。
比如：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 | a | b | c | a | a | b | c | a | b | c | a | a | a | b | d | a | b |
| 前后綴最長公共元素 | 0 | 0 | 0 | 1 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 5 | 6 | 2 | 0 | 1 | 2 |
2.求next數(shù)組
next 數(shù)組考慮的是除當前字符外的最長相同前綴后綴纪挎，所以通過第①步驟求得各個前綴后綴的公共元素的最大長度后，只要稍作變形即可：將第①步驟中求得的值整體右移一位跟匆，然后初值賦為-1异袄，如下表格所示：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 模式串 | a | b | c | a | a | b | c | a | b | c | a | a | a | b | d | a | b |
| next[j] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 2 | 1 | 2 |
3.如何求next函數(shù)值
- next[1] = 0;表明主串從下一字符si+1起和模式串重新開始匹配。i = i+1; j = 1;</p>
-
設next[j] = k玛臂，則next[j+1] = ?</p>
①若pk=pj烤蜕，則有“p1…pk-1pk”=“pj-k+1…pj-1pj” ，如果在
j+1發(fā)生不匹配垢揩，說明next[j+1] = k+1 = next[j]+1玖绿。</p>
②若pk≠pj，可把求next值問題看成是一個模式匹配問
題叁巨，整個模式串既是主串斑匪，又是子串。</p>
在這里插入圖片描述
若pk’=pj锋勺，則有“p1…pk’”=“pj-k’+1…pj”蚀瘸，
next[j+1]=k’+1=next[k]+1=next[next[j]]+1.</p>
若pk”=pj ，則有“p1…pk””=“pj-k”+1…pj”庶橱，
next[j+1]=k”+1=next[k’]+1=next[next[k]]+1.
next[j+1]=1.</p>
4.總結
核心的點在于：以前的bf算法是需要i進行回溯贮勃，導致時間復雜度O(m*n) ,現(xiàn)在kmp算法的核心是i不進行回溯，而j這個值不確定苏章，根據串的規(guī)律寂嘉，主串前面匹配成功的串前綴和后綴相等的地方不需要匹配即可。這樣的時間復雜度是O(m + n)
引用博客例子：
1.最開始匹配時</p>
P[0]跟S[0]匹配失敗</p>
所以執(zhí)行“如果j != -1枫绅，且當前字符匹配失斎ⅰ（即S[i] != P[j]），則令 i 不變并淋，j = next[j]”寓搬，所以j = -1，故轉而執(zhí)行“如果j = -1县耽，或者當前字符匹配成功（即S[i] == P[j]）句喷，都令i++镣典，j++”，得到i = 1唾琼，j = 0兄春，即P[0]繼續(xù)跟S[1]匹配。</p>
P[0]跟S[1]又失配父叙，j再次等于-1神郊，i、j繼續(xù)自增趾唱，從而P[0]跟S[2]匹配。</p>
P[0]跟S[2]失配后蜻懦，P[0]又跟S[3]匹配甜癞。</p>
P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功宛乃，開始執(zhí)行此條指令的后半段：“如果j = -1悠咱，或者當前字符匹配成功（即S[i] == P[j]），都令i++征炼，j++”析既。</p>
2.P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功, ...谆奥，直到當匹配到P[6]處的字符D時失配（即S[10] != P[6]）眼坏，由于P[6]處的D對應的next 值為2，所以下一步用P[2]處的字符C繼續(xù)跟S[10]匹配酸些，相當于向右移動：j - next[j] = 6 - 2 =4 位宰译。
3.向右移動4位后，P[2]處的C再次失配魄懂，由于C對應的next值為0沿侈，所以下一步用P[0]處的字符繼續(xù)跟S[10]匹配，相當于向右移動：j - next[j] = 2 - 0 = 2 位市栗。
4.移動兩位之后缀拭，A 跟空格不匹配，模式串后移1 位填帽。
5.P[6]處的D再次失配蛛淋，因為P[6]對應的next值為2，故下一步用P[2]繼續(xù)跟文本串匹配盲赊，相當于模式串向右移動 j - next[j] = 6 - 2 = 4 位铣鹏。
6.匹配成功，過程結束哀蘑。
匹配過程一模一樣诚卸。也從側面佐證了葵第，next 數(shù)組確實是只要將各個最大前綴后綴的公共元素的長度值右移一位，且把初值賦為-1 即可合溺。
代碼如下：
void get_next(SString T, int &next[])
{
i= 1; next[1] = 0; j = 0;
while( i<T[0]){
if(j==0 || T[i] == T[j]){
++i; ++j;
next[i] = j;
}
else
j = next[j];
}
}
kMP算法的時間復雜度
設主串s的長度為n,模式串t長度為m,在KMP算法中求next數(shù)組的時間復雜度為O(m),在后面的匹配中因主串s的下標不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時間復雜度為O(n+m)
參考原文：https://blog.csdn.net/v_july_v/article/details/7041827?utm_source=copy
