kmp算法詳解（以下標(biāo)為0開始的字符串舉例）

什么是KMP算法呢寸齐？

Knuth-Morris-Pratt 字符串查找算法，簡稱為 KMP算法塞帐，常用于在一個(gè)文本串 S 內(nèi)查找一個(gè)模式串 P 的出現(xiàn)位置制恍。
這個(gè)算法由 Donald Knuth、Vaughan Pratt臣镣、James H. Morris 三人于 1977 年聯(lián)合發(fā)表，故取這 3 姓氏命名此算法智亮。
KMP算法就是一種模式匹配的算法忆某，它可以將傳統(tǒng)的模式匹配算法的時(shí)間復(fù)雜度降低至 O(n+m),采用了空間換時(shí)間的方法。

接下來我將以傳統(tǒng)的模式匹配算法為切入點(diǎn)逐步講解KMP算法

一：基礎(chǔ)知識(shí)

什么是子串阔蛉？

串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串弃舒。如abcd是abcde的字串，而abce不是馍忽。

什么是字符串的模式匹配呢棒坏？

$給定兩個(gè)串S=“s_0s_1s_2s_3 …s_n”和T=“t_0t_1t_2t_3 …t_n”，在主串S中尋找子串T的過程叫做模式匹配遭笋，T稱為模式坝冕。$

二：BF算法（較為暴力的匹配算法）

該方法較為暴力，其核心的思想就是將S和T一個(gè)字符的進(jìn)行匹配瓦呼，若當(dāng)前匹配失敗喂窟，該，T央串、下標(biāo)回溯繼續(xù)匹配磨澡，直到在S中找到T，或者超出S和T長度质和。

具體算法如下：

設(shè)字符串T(下標(biāo)為 j )稳摄，S(下表為 i )，初始化時(shí)i = 0饲宿，j = 0,當(dāng)S[i] == T[j] 時(shí)厦酬，i++，j++瘫想，若不等于則回溯仗阅，j =0，i = i-j+1(S中上一次開始的下一個(gè))国夜，具體代碼如下:
int BF(string S,string T){
  int len_S = S.length();//S的長度 
  int len_T = T.length();//T的長度 
  int i = 0;//S的下標(biāo) 
  int j = 0;//T的下標(biāo) 
  while(i<len_S && j<len_T){//不超出S和T長度且下標(biāo)從0開始
      if(S[i]==T[j]){
          i++;
          j++;
      }else{
          i = i-j+1;
          j = 0;
      }
  }
  if(j>=len_T) return i-j;//返回T在S中的第一元素的坐標(biāo) 
  else return false;//沒有找到 
} 

以S = ababce减噪，T = abc舉例。

1.S[0] == T[0] ,則 i = 1车吹，j = 1

2.S[1] == T[1],則 i = 2筹裕，j = 2

3.S[2] != T[2] ,則 i = i-j+1 = 1, j = 0

4.S[1] != T[0], 則 i = i-j+1 = 2, j = 0

5.S[2] == T[0] ,則 i = 3 ，j = 1

6.S[3] == T[1], 則 i =4 礼搁，j = 2

7.S[4] == T[2],則 i = 5饶碘，j = 3

8.此時(shí) j == len_T 結(jié)束while（）循環(huán)

9.if中判斷為真，在S中找到了T字串馒吴，返回 i-j = 2

BF算法的分析

BF算法雖然簡單扎运，較好理解，但是在一些場合下效率極其低下饮戳，如S = “0000000001“豪治，T=“0000000000000000000000000000001”

每趟比較都會(huì)在T的最后一個(gè)字符‘1’出現(xiàn)不等，所以需要一直重復(fù)扯罐，O(n*m),其中n時(shí)S的長度负拟，m是T的長度。

所以該算法效率較為低下歹河。

1977年Donald Knuth掩浙、Vaughan Pratt花吟、James H. Morris 三人聯(lián)合發(fā)表了一種效率及其高效的算法，簡稱為KMP算法厨姚，該算法的時(shí)間復(fù)雜度為O(n+m)衅澈。

三：KMP算法

KMP算法的改進(jìn)之處

KMP算法改進(jìn)在于：每當(dāng)從某個(gè)起始位置開始一趟比較后，在匹配過程中出現(xiàn)失配谬墙，不回溯i今布，而是利用已經(jīng)得到的部分匹配結(jié)果，將一種假想的位置定位“指針”在模式上向右滑動(dòng)盡可能遠(yuǎn)的一段距離到某個(gè)位置后拭抬，繼續(xù)按規(guī)則進(jìn)行下一次的比較部默。從而達(dá)到降低時(shí)間復(fù)雜度的目的。

在介紹KMP算法之前造虎，我們先來認(rèn)識(shí)最大公共前后綴

前綴：除開最后一個(gè)字符的所有子串,且必須從第一個(gè)字符開始傅蹂。

后綴：除開第一個(gè)字符的所有字串，且必須由最后一個(gè)字符結(jié)束

最大公共前后綴：一個(gè)字符串中所有前后綴的交集算凿。

下面我將以書中T = “abaabcac”舉例來說明贬派。

T的子串	前綴	后綴	最大公共前后綴
a	無	無	0
ab	a	b	0
aba	a,ab	a,ba	1
abaa	a,ab,aba	a,aa,baa	1
abaab	a,ab,aba,abaa	b,ab,aab,baab	2
abaabc	a,ab,aba,abaa,abaab	c,bc,abc,aabc,baabc	0
abaabca	a,ab,aba,abaa,abaab,abaabc	a,ca,bca,abca,aabca,baabca	1
abaabcac	a,ab,aba,abaa,abaab,abaabc,abaabca	c,ac,cac,bcac,abcac,aabcac,baabcac	0

所以可以得出下表

字符	a	b	a	a	b	c	a	c
最大公共前后綴	0	0	1	1	2	0	1	0

為什么書中的其他情況是1呢？

這是因?yàn)樵诮滩闹械淖址南聵?biāo)是從1開始的澎媒，而這里是從0為下標(biāo)開始的搞乏。

知道什么是最大公共前后綴后，接下來就是next[j]數(shù)組的介紹

若令next[j] = k,則next[j]表明當(dāng)前模式中第 j+1 （下標(biāo)從0開始）個(gè)字符與主串中相應(yīng)字符“匹配失敗時(shí)”戒努，在模式中需要重新和主串中該字符比較的位置请敦。這就是KMP算法的核心。

那我們應(yīng)該如何得到next[j]呢储玫？

只需要將最大公共前后綴表中的最大公共前后綴向右移動(dòng)一位即可侍筛。因?yàn)楫?dāng)此時(shí) j 匹配失敗時(shí)，需要前一個(gè)字符串的最大公共前后綴撒穷。

next[j]

字符	a	b	a	a	b	c	a	c
next[j]	-1	0	0	1	1	2	0	1

下面是對(duì)KMP過程的模擬

設(shè)T = ‘’abaabcac" , S = "acabaabaabcacaabc",當(dāng)S[i] == T[j]或者 j == -1時(shí)匣椰，i++，j++端礼。否則 j = next[j]

一：主串：acabaabaabcacaabc

? 模式： abaabcac

? 在 i = 1禽笑，j = 1 匹配失敗，j = next[1] = 0

二：主串：acabaabaabcacaabc

? 模式： abaabcac

? 在 i = 1蛤奥，j = 0匹配失敗佳镜，j = 0 ， i = 2

三：主串：acabaabaabcacaabc

? 模式： abaabcac

? 在i = 7凡桥，j = 5匹配失敗蟀伸， i = 7，j = next[5] = 2

四：主串：acabaabaabcacaabc

? 模式： abaabcac
此時(shí)i=5

? 匹配成功。

代碼如下：

int KMP(string S,string T){
    int len_S = S.length();//S的長度 
    int len_T = T.length();//T的長度 
    int i = 0;//S的下標(biāo) 
    int j = 0;//T的下標(biāo) 
    while(i<len_S && j<len_T){//不超出S和T長度且下標(biāo)從0開始
        if(S[i]==T[j]|| j == -1){
            i++;
            j++;
        }else{
            j = next[j]
        }
    }
    if(j>=len_T) return i - len_T;//返回T在S中的第一元素的坐標(biāo) 
    else return false;//沒有找到 
}

那么為什么可以使用next[j]來進(jìn)行模式匹配呢啊掏？

當(dāng)前匹配失敗時(shí)章郁，我們可以查看前一個(gè)字符串的公共最大前后綴來確定向右移動(dòng)的位置参淫，因?yàn)樵谇耙粋€(gè)字符串已經(jīng)與S匹配了双仍，而我們又有相同的前后綴長度蟀俊，則可以直接將前綴移動(dòng)到后綴的位置，之后從下一個(gè)字符開始匹配小泉，這樣就可達(dá)到向右盡可能地移動(dòng)。

比如：[

image.png

next[j]的求法

next[j] = k 表明有以下關(guān)系： $'p_0p_1...p_{k-1}=p_{j-k}...p_{j-1}'$

(1):當(dāng) $p_k =p_j$ 時(shí)冕杠，next[j+1] = k+1

(2):若 $p_k\neq p_j$ 時(shí)微姊，說明當(dāng)前字符串中沒有長度k+1的最大公共前后綴，這樣我們就只有找更短的前后綴了分预。

? 此時(shí)我們將求next的值看作為一個(gè)求模式匹配的問題兢交，整個(gè)模式串既是主串又是模式串，在匹配的過程中笼痹，已有 $p_0=p_{j-k},...,p_{k-1}=p_{j-1}$ ,則當(dāng) $p_k \neq p_j$ 時(shí)模式串應(yīng)移動(dòng)到next[k]個(gè)字符和主串中的第j個(gè)字符相比較配喳，若 $p_{next[k]=p_j}$ ，則說明在j+1之前存在一個(gè)更短的最大公共前后綴凳干，令 $k^{'} = next[k]$ ,則 $'p_0p_1...p_{k^{'}-1}=p_{j-k^{'}}...p_{j-1}'$ ,則 $next[j+1] = k^{'}+1$ ,即next[j+1] = next[k] + 1晴裹。若找不到，則next[j+1] = 0救赐。

代碼如下
void get_next(string T,int next[]){
  int i = 0;
  int j = -1; //next的值
  next[0] = -1;//初始化next[0] = -1
  while(i<T.length()-1){
      if(j==-1||T[i]==T[j]){//T[i]表示后綴涧团，T[j]表示前綴   
          i++;
          j++;
          next[i] = j;
      }else{
          j = next[j];//不相等時(shí)，尋找更短的最大公共前后綴经磅。
      }
  }
} 

next[j]的改進(jìn)

當(dāng)出現(xiàn)S = “a a b a a a a b” , T = " a a a a b" 時(shí)泌绣，當(dāng) i = 3, j = 3 時(shí)，匹配失敗预厌，但是此時(shí)的T中的a匹配阿迈，但是當(dāng)j = next[3] 時(shí)，T[j]還是等于 a 轧叽，這樣就產(chǎn)生了重復(fù)比較苗沧，這里就是對(duì)next的改進(jìn)的地方。設(shè)next[j] = k,如果T[i] == T[j] ,則不在與T[k]比比較炭晒，而是直接與T[next[k]]比較崎页，就是說 next[j] = next[k],所以代碼如下：
void get_nextval(string T,int next[]){
  int i = 0;
  int j = -1; //next的值
  nextval[0] = -1;//初始化nextval[0] = -1
  while(i<T.length()-1){
      if(j==-1||T[i]==T[j]){//T[i]表示后綴，T[j]表示前綴   
          i++;
          j++;
          if(T[i]!=T[j]) nextval[i] = j;
          else nextval[i] = nextval[j];//不相等時(shí)
      }else{
          j = next[j];
      }
  }
} 

以上就是我對(duì)KMP算法的理解

完整代碼

#include<iostream>
#include<cstring>
using namespace std;
string S = "acabaabaabcacaabc";
string T = "abaabcac";
int nextval[100];
int KMP(string S,string T){
    int len_S = S.length();//S的長度 
    int len_T = T.length();//T的長度 
    int i = 0;//S的下標(biāo) 
    int j = 0;//T的下標(biāo) 
    while(i<len_S && j<len_T){//不超出S和T長度且下標(biāo)從0開始
        if(S[i]==T[j]|| j == -1){
            i++;
            j++;
        }else{
            j = nextval[j];
        }
    }
    if(j>=len_T) return i - len_T;//返回T在S中的第一元素的坐標(biāo) 
    else return false;//沒有找到 
} 
void get_nextval(string T,int next[]){
    int i = 0;
    int j = -1; //next的值
    nextval[0] = -1;//初始化nextval[0] = -1
    while(i<T.length()-1){
        if(j==-1||T[i]==T[j]){//T[i]表示后綴腰埂，T[j]表示前綴   
            i++;
            j++;
            if(T[i]!=T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }else{
            j = next[j];
        }
    }
} 
int main(void){
    get_nextval(T,nextval);
    cout<<"T在S中的第"<<KMP(S,T)+1<<"號(hào)位置上";
    return 0;
}