title: 串的模式匹配算法之kmp
tags: 數(shù)據(jù)結(jié)構(gòu)與算法之美
author: 辰砂tj

1.引言

首先我們需要了解串的模式算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）；常見(jiàn)的算法種類：
BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的），KMP算法（特點(diǎn)：速度快）。網(wǎng)上有很多帖子，博客寫的都特別好，這篇文章也是對(duì)自己的一個(gè)總結(jié)。

2.BF算法

BF算法設(shè)計(jì)思想：

將主串的第pos個(gè)字符和模式的第一個(gè)字符比較 </br>
若相等，繼續(xù)逐個(gè)比較后續(xù)字符；</br>
若不等，從主串的下一字符起，重新與模式的第一個(gè)字符比較。 </br>
直到主串的一個(gè)連續(xù)子串字符序列與模式相等 。</br>
返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。</br>
否則，匹配失敗，返回值 0

1.舉例：

假設(shè)現(xiàn)在我們面臨這樣一個(gè)問(wèn)題：有一個(gè)文本串S，和一個(gè)模式串P，現(xiàn)在要查找P在S中的位置，怎么查找呢？</p>

如果用暴力匹配的思路，并假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置，則有：

如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續(xù)匹配下一個(gè)字符；

如果失配（即S[i]! = P[j]），令i = i - (j - 1) （表示主串的位置回到當(dāng)前的下一個(gè)位置），j = 0。相當(dāng)于每次匹配失敗時(shí)，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]) {
                //①如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++
                i++;
                j++;
            } else {
                //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
                // i - (j - 1) 表示主串的位置回到當(dāng)前的下一個(gè)位置。
                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.時(shí)間復(fù)雜度說(shuō)明：

若n為主串長(zhǎng)度，m為子串長(zhǎng)度，最壞情況是
主串前面n-m個(gè)位置都部分匹配到子串的最后一位，即這n-m位各比較了m次
最后m位也各比較了1次

總次數(shù)為：(n-m)m+m＝(n-m+1)m
若m<<n，則算法復(fù)雜度O(n*m)

網(wǎng)上有個(gè)很好的例子，故引用：

舉個(gè)例子，如果給定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，現(xiàn)在要拿模式串P去跟文本串S匹配，整個(gè)過(guò)程如下所示：

1.S[0]為B，P[0]為A，不匹配，執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相當(dāng)于模式串要往右移動(dòng)一位（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），從而模式串不斷的向右移動(dòng)一位（不斷的執(zhí)行“令i = i - (j - 1)，j = 0”，i從2變到4，j一直為0）

在這里插入圖片描述

3.直到S[4]跟P[0]匹配成功（i=4，j=0），此時(shí)按照上面的暴力匹配算法的思路，轉(zhuǎn)而執(zhí)行第①條指令：“如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++”，可得S[i]為S[5]，P[j]為P[1]，即接下來(lái)S[5]跟P[1]匹配（i=5，j=1）

在這里插入圖片描述

4.S[5]跟P[1]匹配成功，繼續(xù)執(zhí)行第①條指令：“如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此進(jìn)行下去

在這里插入圖片描述

5.直到S[10]為空格字符，P[6]為字符D（i=10，j=6），因?yàn)椴黄ヅ?，重新?zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相當(dāng)于S[5]跟P[0]匹配（i=5，j=0）

在這里插入圖片描述

6.至此，我們可以看到，如果按照暴力匹配算法的思路，盡管之前文本串和模式串已經(jīng)分別匹配到了S[9]、P[5]，但因?yàn)镾[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，從而讓S[5]跟P[0]匹配。

在這里插入圖片描述

而S[5]肯定跟P[0]失配。為什么呢？因?yàn)樵谥暗?步匹配中，我們已經(jīng)得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯過(guò)去必然會(huì)導(dǎo)致失配。那有沒(méi)有一種算法，讓i 不往回退，只需要移動(dòng)j 即可呢？

3.KMP算法（主串指針不回溯）

算法思想：利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動(dòng)速度？且主串S的指針i不必回溯！可提速到O(n+m)！

算法步驟：
下面先直接給出KMP的算法流程：

假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置 </p>

如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續(xù)匹配下一個(gè)字符； </p>

如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時(shí)，模式串P相對(duì)于文本串S向右移動(dòng)了j - next [j] 位。 </p>

換言之，當(dāng)匹配失敗時(shí)，模式串向右移動(dòng)的位數(shù)為：失配字符所在位置 - 失配字符對(duì)應(yīng)的next 值（next 數(shù)組的求解會(huì)在下文的3.3.3節(jié)中詳細(xì)闡述），即移動(dòng)的實(shí)際位數(shù)為：j - next[j]，且此值大于等于1。 </p>

很快，你也會(huì)意識(shí)到next 數(shù)組各值的含義：代表當(dāng)前字符之前的字符串中，有多大長(zhǎng)度的相同前綴后綴。例如如果next [j] = k，代表j 之前的字符串中有最大長(zhǎng)度為k 的相同前綴后綴。

此也意味著在某個(gè)字符失配時(shí)，該字符對(duì)應(yīng)的next 值會(huì)告訴你下一步匹配中，模式串應(yīng)該跳到哪個(gè)位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，則跳到模式串的開(kāi)頭字符，若next [j] = k 且 k > 0，代表下次匹配跳到j(luò) 之前的某個(gè)字符，而不是跳到開(kāi)頭，且具體跳過(guò)了k 個(gè)字符。

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]) {
                //①如果當(dāng)前字符匹配成功（即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ù)，表明當(dāng)模式中第j個(gè)字符與主串中相應(yīng)字符“失配”時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符的位置。

1.如何求next()?

1.尋找前綴后綴最長(zhǎng)公共元素長(zhǎng)度

比如 字符串 ‘a(chǎn)’ 的前綴就是為空，后綴也是為空，所以前綴后綴的意思，是不包括當(dāng)前字符串，字符串 ‘a(chǎn)b’ 的前綴是a，后綴是b。

定義： 對(duì)于P = p0 p1 ...pj-1 pj，尋找模式串P中長(zhǎng)度最大且相等的前綴和后綴。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大長(zhǎng)度為k+1的相同前綴后綴。

比如：

2.求next數(shù)組

next 數(shù)組考慮的是除當(dāng)前字符外的最長(zhǎng)相同前綴后綴，所以通過(guò)第①步驟求得各個(gè)前綴后綴的公共元素的最大長(zhǎng)度后，只要稍作變形即可：將第①步驟中求得的值整體右移一位，然后初值賦為-1，如下表格所示：

在這里插入圖片描述

3.如何求next函數(shù)值

1. next[1] = 0;表明主串從下一字符si+1起和模式串重新開(kāi)始匹配。i = i+1; j = 1;</p>

2. 設(shè)next[j] = k，則next[j+1] = ?</p>
   ①若pk=pj，則有“p1…pk-1pk”=“pj-k+1…pj-1pj” ，如果在
   j+1發(fā)生不匹配，說(shuō)明next[j+1] = k+1 = next[j]+1。</p>
   ②若pk≠pj，可把求next值問(wèn)題看成是一個(gè)模式匹配問(wèn)
   題，整個(gè)模式串既是主串，又是子串。</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.總結(jié)

核心的點(diǎn)在于：以前的bf算法是需要i進(jìn)行回溯，導(dǎo)致時(shí)間復(fù)雜度O(m*n) ,現(xiàn)在kmp算法的核心是i不進(jìn)行回溯，而j這個(gè)值不確定，根據(jù)串的規(guī)律，主串前面匹配成功的串前綴和后綴相等的地方不需要匹配即可。這樣的時(shí)間復(fù)雜度是O(m + n)

引用博客例子：

1.最開(kāi)始匹配時(shí)</p>
P[0]跟S[0]匹配失敗</p>
所以執(zhí)行“如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]”，所以j = -1，故轉(zhuǎn)而執(zhí)行“如果j = -1，或者當(dāng)前字符匹配成功（即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]匹配成功，開(kāi)始執(zhí)行此條指令的后半段：“如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++”。</p>

在這里插入圖片描述

2.P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功, ...，直到當(dāng)匹配到P[6]處的字符D時(shí)失配（即S[10] != P[6]），由于P[6]處的D對(duì)應(yīng)的next 值為2，所以下一步用P[2]處的字符C繼續(xù)跟S[10]匹配，相當(dāng)于向右移動(dòng)：j - next[j] = 6 - 2 =4 位。

在這里插入圖片描述

3.向右移動(dòng)4位后，P[2]處的C再次失配，由于C對(duì)應(yīng)的next值為0，所以下一步用P[0]處的字符繼續(xù)跟S[10]匹配，相當(dāng)于向右移動(dòng)：j - next[j] = 2 - 0 = 2 位。

在這里插入圖片描述

4.移動(dòng)兩位之后，A 跟空格不匹配，模式串后移1 位。

在這里插入圖片描述

5.P[6]處的D再次失配，因?yàn)镻[6]對(duì)應(yīng)的next值為2，故下一步用P[2]繼續(xù)跟文本串匹配，相當(dāng)于模式串向右移動(dòng) j - next[j] = 6 - 2 = 4 位。

在這里插入圖片描述

6.匹配成功，過(guò)程結(jié)束。

在這里插入圖片描述

匹配過(guò)程一模一樣。也從側(cè)面佐證了，next 數(shù)組確實(shí)是只要將各個(gè)最大前綴后綴的公共元素的長(zhǎng)度值右移一位，且把初值賦為-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算法的時(shí)間復(fù)雜度

設(shè)主串s的長(zhǎng)度為n,模式串t長(zhǎng)度為m,在KMP算法中求next數(shù)組的時(shí)間復(fù)雜度為O(m),在后面的匹配中因主串s的下標(biāo)不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時(shí)間復(fù)雜度為O(n+m)

參考原文：https://blog.csdn.net/v_july_v/article/details/7041827?utm_source=copy