??在文本處理中，關(guān)鍵字匹配是一個(gè)十分常用且重要的功能。關(guān)鍵字稱為模式串，在文本T中尋找模式串P出現(xiàn)的所有出現(xiàn)的位置，解決這種問題的算法叫做字符串匹配算法。字符串匹配算法可以說是計(jì)算機(jī)科學(xué)中最古老、研究最廣泛的問題之一，并且字符串匹配的應(yīng)用也隨處可見，特別是信息檢索領(lǐng)域和計(jì)算生物學(xué)領(lǐng)域。
??模式匹配算法有很多很多，其中比較著名的算法有：KMP（Knuth-Morris-Pratt）算法，BM（Boyer-Moore）算法，Sunday 算法和Horspool算法。接下來將簡單介紹模式匹配中的幾種常見的算法。

1.樸素匹配算法

??樸素匹配算法是一種暴力匹配方法，從文本的開頭通過依次比較的方式向后對(duì)模式串進(jìn)行匹配。樸素匹配算法是一種比較容易想到且實(shí)現(xiàn)比較容易的方法，假設(shè)文本T長度為m，模式串P長度為n。算法從文本第1位從左向右開始與模式串P進(jìn)行匹配，無論是否匹配成功，模式串都后移1位開始繼續(xù)進(jìn)行重新匹配，總共進(jìn)行m-n+1次匹配。算法極其簡單，因此效率極其有限，時(shí)間復(fù)雜度為O(m*n)，故不常被用，這里不做詳細(xì)介紹。

2.KMP算法

??KMP算法是由三名科學(xué)家（Knuth，Morris，Pratt）聯(lián)合提出的模式匹配方法。KMP是一種相對(duì)高效的模式匹配算法，它的高性能的原因在于它可以通過利用字符串匹配過程中的失敗信息來減少模式匹配的次數(shù)，進(jìn)而提升匹配性能。
??KMP算法借助了一個(gè)輔助的結(jié)構(gòu)——部分匹配表，部分匹配表是針對(duì)模式串產(chǎn)生的一個(gè)輔助信息表，通過該表，可以在匹配失敗時(shí)，降低無用的匹配次數(shù)。部分匹配表的長度與模式串長度相同，部分匹配子是當(dāng)前字符對(duì)應(yīng)的“前綴”和“后綴”的最長公共元素的個(gè)數(shù)。
??假設(shè)現(xiàn)在有個(gè)模式串“圈圈大師”，我們可以通過如下的過程得到部分匹配表：
（1）對(duì)于第一個(gè)“圈”，它的前綴和后綴都為空，因此共有元素的數(shù)目為0，所以第一個(gè)“圈”的部分匹配值為0；
（2）對(duì)于“圈圈”，它的前綴為“圈”，后綴為“圈”，共有元素的數(shù)目為1，所以第二個(gè)“圈”的部分匹配值為1；
（3）對(duì)于“圈圈大”，它的前綴為“圈”、“圈圈”，后綴為“大”、“圈大”，共有元素的數(shù)目為0，因此第三個(gè)字的部分匹配值為0；
（4）對(duì)于“圈圈大師”，它的前綴為“圈”、“圈圈”、“圈圈大”，后綴為“師”、“大師”，“圈大師”。共有元素的數(shù)目為0，因此第四個(gè)字的部分匹配值為0；
以上，我們可以得到如下的部分匹配表。

??部分匹配表是KMP算法進(jìn)行字符串查找的重要參考依據(jù)，因此有了部分匹配表之后，我們可以對(duì)文本“畫圈圈的圈圈大師傅”進(jìn)行模式串“圈圈大師”的匹配。匹配方式為：
??每次開始從左向右匹配，若前k位匹配成功，則 后移位數(shù)s = 當(dāng)前已匹配的字符數(shù)k - 最后一個(gè)匹配字的部分匹配值。
匹配過程如下：

step1：
畫圈圈大的圈圈大師
圈圈大師

step2：
畫圈圈大的圈圈大師
〇圈圈大師

step3：
畫圈圈大的圈圈大師
〇〇〇〇圈圈大師

step4：
畫圈圈大的圈圈大師
〇〇〇〇〇圈圈大師

??KMP算法分為兩個(gè)步驟，先通過P計(jì)算出部分匹配表，時(shí)間復(fù)雜度為O(n)；再通過此表進(jìn)行匹配位移，時(shí)間復(fù)雜度為O(m)，故理論上的總時(shí)間復(fù)雜度為O(m+n)，達(dá)到線性效率。理論效率高，但實(shí)際上卻未特別突出。
KMP代碼實(shí)現(xiàn)如下(JAVA)：

3.Boyer-Moore算法

??Boyer-Moore算法簡稱為BM算法，是一種與KMP算法同等重要的模式匹配算法。BM算法相對(duì)于KMP算法效率更高，且更容易理解和實(shí)現(xiàn)。
??與KMP有兩個(gè)不同點(diǎn)：
??①每次匹配時(shí)，匹配方向不同，BM算法每次從右向左匹配，此類算法隸屬于基于后綴搜索的方法。
??②匹配后向后偏移的位數(shù)由兩種計(jì)算方式得到：壞字符偏移和好后綴偏移。

step1:
HERE IS A SIMPLE EXAMPLE
EXAMPLE

??首先，原字符串和子串左端對(duì)齊，但是從尾部開始比較，就是首先比較“S”和“E”，這是一個(gè)十分巧妙的做法，如果字符串不匹配的話，只需要這一次比較就可以確定。
??在BM算法中，當(dāng)每次發(fā)現(xiàn)當(dāng)前字符不匹配的時(shí)候，我們就需要尋找一下子串中是否有這個(gè)字符；比如當(dāng)前“S”和“E”不匹配，那我們需要尋找一下子串當(dāng)中是否存在“S”。發(fā)現(xiàn)子串當(dāng)中并不存在，那我們將子串整體向后移動(dòng)到原字符串中“S”的下一個(gè)位置：

step2:
HERE IS A SIMPLE EXAMPLE
       EXAMPLE

??我們接著從尾部開始比較，發(fā)現(xiàn)“P”和“E”不匹配，那我們查找一下子串當(dāng)中是否存在“P”，發(fā)現(xiàn)存在，那我們就把子串移動(dòng)到兩個(gè)“P”對(duì)齊的位置：

step3:
HERE IS A SIMPLE EXAMPLE
         EXAMPLE

??依然從尾部開始比較，“E”匹配，“L”匹配，“P”匹配，“M”匹配，“I”和“A”不匹配！那我們就接著尋找一下子串當(dāng)前是否出現(xiàn)了原字符串中的字符，我們發(fā)現(xiàn)子串中第一個(gè)“E”和原字符串中的字符可以對(duì)應(yīng)，那直接將子串移動(dòng)到兩個(gè)“E”對(duì)應(yīng)的位置：

step4:
HERE IS A SIMPLE EXAMPLE
               EXAMPLE

??從尾部比較，發(fā)現(xiàn)“P”和“E”不匹配，那么檢查一下子串當(dāng)中是否出現(xiàn)了“P”，發(fā)現(xiàn)存在，那么移動(dòng)子串到兩個(gè)“P”對(duì)應(yīng)：

step5:
HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

??從尾部開始，逐個(gè)匹配，發(fā)現(xiàn)全部能匹配上，匹配成功！
??目前很多的文本編輯器中的查找方法都是基于BM算法實(shí)現(xiàn)的，相對(duì)于KMP算法，其實(shí)用性更高，且效率通常為KMP算法的3~5倍。
BM算法代碼實(shí)現(xiàn)如下(JAVA)：

4.Sunday算法

step1:
HERE IS A SIMPLE EXAMPLE
EXAMPLE

??首先原字符串和子串左端對(duì)齊，發(fā)現(xiàn)“T”與“E”不匹配之后，檢測原字符串中下一個(gè)字符（在這個(gè)例子中是“IS”后面的那個(gè)空格）是否在子串中出現(xiàn)，如果出現(xiàn)移動(dòng)子串將兩者對(duì)齊，如果沒有出現(xiàn)則直接將子串移動(dòng)到下一個(gè)位置。這里空格沒有在子串中出現(xiàn)，移動(dòng)子串到空格的下一個(gè)位置“A”：

step2:
HERE IS A SIMPLE EXAMPLE
        EXAMPLE

??發(fā)現(xiàn)“A”與“E”不匹配，但是原字符串中下一個(gè)字符“E”在子串中出現(xiàn)了，第一個(gè)字符和最后一個(gè)字符都有出現(xiàn)，那么首先移動(dòng)子串靠后的字符與原字符串對(duì)齊：

step3:
HERE IS A SIMPLE EXAMPLE
         EXAMPLE

??發(fā)現(xiàn)空格和“E”不匹配，原字符串中下一個(gè)字符“空格”也沒有在子串中出現(xiàn)，所以直接移動(dòng)子串到空格的下一個(gè)字符“E”：

step4:
HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

??從頭開始逐個(gè)匹配，匹配成功！
??在Sunday算法的比較過程中最核心的點(diǎn)在于：如果當(dāng)前匹配失敗，則根據(jù)模式串與文本的對(duì)應(yīng)部分的后面一個(gè)字符串作為跳轉(zhuǎn)的依據(jù)，如果該字符不在模式串中，則直接略過，模式串直接跳到下一位進(jìn)行匹配；如果該字符在模式串中，怎將模式串對(duì)齊到最后一個(gè)與當(dāng)前字符相同的位置，然后再從頭進(jìn)行比較。
Sunday算法代碼實(shí)現(xiàn)如下(JAVA)：

public static List<Integer> Sunday(String txt, String part){
        List<Integer> locs = new ArrayList<Integer>();
        final int tlen = txt.length();
        final int plen = part.length();
        
        for(int start = 0, newS = 0; start + plen <= tlen; ){
            if(isPattern(start, txt, part)){
                locs.add(start);
                start += plen;
            }else{
                newS = start + plen;
                if(newS >= tlen)
                    break;
                int lIndex = part.lastIndexOf(txt.charAt(newS));
                if(lIndex == -1){
                    start = newS ++;
                }else{
                    start += plen - lIndex;
                }
            }
        }
        return locs;
    }
    
    private static boolean isPattern(int start, String txt, String part){
        boolean isPattern = true;
        
        //異常數(shù)據(jù)排除
        if(null == txt || null == part || start >= txt.length() || start + part.length() > txt.length()){
            isPattern =  false;
        }
        
        //判斷字符串是否匹配
        for(int i = 0; isPattern && i < part.length(); i++){
            if(txt.charAt(i + start) != part.charAt(i)){
                isPattern = false;
                break;
            }
        }
        return isPattern;
    }

參考：
（1）https://www.cnblogs.com/Franky-ln/p/5890201.html