概述

字符串匹配（查找）是字符串的一種基本操作：給定帶匹配查詢的文本串S和目標(biāo)子串T，T也叫做模式串。在文本S中找到一個(gè)和模式T相符的子字符串，并返回該子字符串在文本中的位置。

暴力匹配

Brute Force Algorithm，也叫樸素字符串匹配算法，Naive String Matching Algorithm。
基本思路就是將字符一個(gè)一個(gè)地進(jìn)行比較：

• 如果S和T兩個(gè)字符串的第一個(gè)字符相同就比較第二個(gè)字符,如果相同就一直繼續(xù)；
• 如果其中有某一個(gè)字符不同，則將T字符串向后移一位，將S字符串的第二個(gè)字符與T的字符串的第一個(gè)字符重新開(kāi)始比較。
• 循環(huán)往復(fù)，一直到結(jié)束

實(shí)現(xiàn)

public static int bf(String text, String pattern) {
    int m = text.length();
    int n = pattern.length();
    for (int i = 0; i <= m - n; i++) {
        boolean flag = true;
        for (int j = 0; j < n; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return i;
        }
    }
    return -1;
}

KMP

D.E.Knuth，J.H.Morris 和 V.R.Pratt發(fā)明，一種字符串匹配的改進(jìn)算法，利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。KMP算法只需要對(duì)文本串搜索一次，時(shí)間復(fù)雜度是O(n)。

KMP 算法的關(guān)鍵是求 next 數(shù)組。next 數(shù)組的長(zhǎng)度為模式串的長(zhǎng)度。next 數(shù)組中每個(gè)值代表模式串中當(dāng)前字符前面的字符串中，有多大長(zhǎng)度的相同前綴后綴。

原理

暴力匹配
給定字符串A和B，判斷B是否是A的子串。暴力匹配的方法：從A的第一個(gè)字符開(kāi)始，比較A的第一個(gè)字符和B的第一個(gè)字符是否相同，相同則比較A的第二個(gè)字符和B的第二個(gè)字符，不相同，則從A的第二個(gè)字符開(kāi)始，與B的第一個(gè)字符開(kāi)始比較。以此類推。相當(dāng)于一步步右移B的動(dòng)作。

暴力匹配，效率低，體現(xiàn)在一步步移動(dòng)，尤其是在B的前n-1個(gè)字符都能匹配成功，最后一個(gè)字符匹配失敗，或B子串較長(zhǎng)的情況下。KMP利用匹配表的概念來(lái)優(yōu)化匹配效率。

匹配表
對(duì)于給定的字符串B，如abcab：

• 前綴：除了最后個(gè)字符外，所有的順序組合方式：a、ab、abc、abca
• 后綴：除了第一個(gè)字符外，所有的順序組合方式：bcab、cab、ab、b

匹配值，對(duì)子串的每個(gè)字符組合尋找出前綴和后綴，比較是否有相同的，相同的字符組合有幾位，匹配值就是幾。

比如針對(duì)給定的字符串abcab，其匹配值字符串為00012：

• a，無(wú)前后綴，匹配值=0
• ab，前綴{a}，后綴，無(wú)共同字符，匹配值=0
• abc，前綴{a}{ab}，后綴{c}{bc}，無(wú)共同字符，匹配值=0
• abca，前綴{a}{ab}{abc}，后綴{a}{ca}{bca}，共同字符{a}，匹配值=1
• abcab，前綴{a}{ab}{abc}{abca}，后綴{ab}{cab}{bcab}，共同字符{ab}，匹配值=2

基于匹配表，不需要一個(gè)個(gè)移動(dòng)，移動(dòng)步數(shù) = 成功匹配的位數(shù) - 匹配表里面的匹配值。

實(shí)現(xiàn)

給出一個(gè)KMP算法實(shí)現(xiàn)：

/**
 * 利用KMP算法求解pattern是否在text中出現(xiàn)過(guò)
 *
 * @param text    文本串
 * @param pattern 模式串
 * @return pattern在text中出現(xiàn)，則返回true，否則返回false
 */
public static boolean kmpSearch(String text, String pattern) {
    // 部分匹配數(shù)組
    int[] partMatchTable = kmpNext(pattern);
    // text中的指針
    int i = 0;
    // pattern中的指針
    int j = 0;
    while (i < text.length()) {
        if (text.charAt(i) == pattern.charAt(j)) {
            // 字符匹配，則兩個(gè)指針同時(shí)后移
            i++;
            j++;
        } else if (j > 0) {
            // 字符失配，則利用next數(shù)組，移動(dòng)j指針，避免i指針回退
            j = partMatchTable[j - 1];
        } else {
            // pattern中的第一個(gè)字符就失配
            i++;
        }
        if (j == pattern.length()) {
            // 搜索成功
            return true;
        }
    }
    return false;
}

private static int[] kmpNext(String pattern) {
    int[] next = new int[pattern.length()];
    next[0] = 0;
    int j=0;
    for (int i = 1; i < pattern.length(); i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)){//前后綴相同
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)){//前后綴不相同
            j++;
        }
        next[i] = j;
    }
    return next;
}

Boyer-Moore

Boyer-Moore 算法在實(shí)際應(yīng)用中比 KMP 算法效率高，據(jù)說(shuō)各種文本編輯器的查找功能，包括Linux 里的 grep 命令，都是采用 Boyer-Moore 算法。該算法有壞字符和好后綴兩個(gè)概念，字符串從后往前匹配。 一般情況下，比KMP算法快3-5倍。

原理

假設(shè)文本串S長(zhǎng)度為n，模式串T長(zhǎng)度為m，BM算法的主要特征為：

• 從右往左進(jìn)行比較匹配（一般的字符串搜索算法如KMP都是從左往右進(jìn)行匹配）；
• 算法分為兩個(gè)階段：預(yù)處理階段和搜索階段；
• 預(yù)處理階段時(shí)間和空間復(fù)雜度都是是O(m+)，是字符集大小，一般為256；
• 搜索階段時(shí)間復(fù)雜度是O(mn)；
• 當(dāng)模式串是非周期性的，在最壞的情況下算法需要進(jìn)行3n次字符比較操作；
• 算法在最好的情況下達(dá)到O(n/m)，即只需要n/m次比較。

而B(niǎo)M算法在移動(dòng)模式串的時(shí)候是從左到右，而進(jìn)行比較的時(shí)候是從右到左的。

BM算法的精華就在于BM(text, pattern)，BM算法當(dāng)不匹配的時(shí)候一次性可以跳過(guò)不止一個(gè)字符。即它不需要對(duì)被搜索的字符串中的字符進(jìn)行逐一比較，而會(huì)跳過(guò)其中某些部分。通常搜索關(guān)鍵字越長(zhǎng)，算法速度越快。它的效率來(lái)自于這樣的事實(shí)：對(duì)于每一次失敗的匹配嘗試，算法都能夠使用這些信息來(lái)排除盡可能多的無(wú)法匹配的位置。即它充分利用待搜索字符串的一些特征，加快搜索的步驟。

BM算法包含兩個(gè)并行的算法（也就是兩個(gè)啟發(fā)策略）：壞字符算法（bad-character shift）和好后綴算法（good-suffix shift）。這兩種算法的目的就是讓模式串每次向右移動(dòng)盡可能大的距離（即BM()盡可能大）。

實(shí)現(xiàn)

/**
 * Boyer-Moore算法是一種基于后綴匹配的模式串匹配算法，后綴匹配就是模式串從右到左開(kāi)始比較，但模式串的移動(dòng)還是從左到右的。
 * 字符串匹配的關(guān)鍵就是模式串的如何移動(dòng)才是最高效的，Boyer-Moore為了做到這點(diǎn)定義了兩個(gè)規(guī)則：壞字符規(guī)則和好后綴規(guī)則<br>
 * 壞字符規(guī)則<bR>
 * 1.如果壞字符沒(méi)有出現(xiàn)在模式字符中，則直接將模式串移動(dòng)到壞字符的下一個(gè)字符：<br>
 * 2.如果壞字符出現(xiàn)在模式串中，則將模式串最靠近好后綴的壞字符（當(dāng)然這個(gè)實(shí)現(xiàn)就有點(diǎn)繁瑣）與母串的壞字符對(duì)齊：<br>
 * 好后綴規(guī)則<bR>
 * 1.模式串中有子串匹配上好后綴，此時(shí)移動(dòng)模式串，讓該子串和好后綴對(duì)齊即可，如果超過(guò)一個(gè)子串匹配上好后綴，則選擇最靠靠近好后綴的子串對(duì)齊。<br>
 * 2.模式串中沒(méi)有子串匹配上后后綴，此時(shí)需要尋找模式串的一個(gè)最長(zhǎng)前綴，并讓該前綴等于好后綴的后綴，尋找到該前綴后，讓該前綴和好后綴對(duì)齊即可。<br>
 * 3.模式串中沒(méi)有子串匹配上后后綴，并且在模式串中找不到最長(zhǎng)前綴，讓該前綴等于好后綴的后綴。此時(shí)，直接移動(dòng)模式到好后綴的下一個(gè)字符。<br>
 */
public static List<Integer> bmMatch(String text, String pattern) {
    List<Integer> matches = new ArrayList<>();
    int m = text.length();
    int n = pattern.length();
    // 生成模式字符串的壞字符移動(dòng)結(jié)果
    Map<Character, Integer> rightMostIndexes = preprocessForBadCharacterShift(pattern);
    // 匹配的節(jié)點(diǎn)位置
    int alignedAt = 0;
    // 如果當(dāng)前節(jié)點(diǎn)在可匹配范圍內(nèi)，即當(dāng)前的A[k]必須在A[0, m-n-1)之間，否則沒(méi)有必要做匹配
    while (alignedAt + (n - 1) < m) {
        // 循環(huán)模式組，查詢模式組是否匹配 從模式串的最后面開(kāi)始匹配，并逐漸往前匹配
        for (int indexInPattern = n - 1; indexInPattern >= 0; indexInPattern--) {
            // 1 定義待查詢字符串中的當(dāng)前匹配位置.
            int indexInText = alignedAt + indexInPattern;
            // 2 驗(yàn)證帶查詢字符串的當(dāng)前位置是否已經(jīng)超過(guò)最長(zhǎng)字符，如果超過(guò)，則表示未查詢到.
            if (indexInText >= m) {
                break;
            }
            // 3 獲取到帶查詢字符串和模式字符串中對(duì)應(yīng)的待匹配字符
            char x = text.charAt(indexInText);
            char y = pattern.charAt(indexInPattern);
            // 4 驗(yàn)證結(jié)果
            if (x != y) {
                // 4.1 如果兩個(gè)字符串不相等，則尋找最壞字符串的結(jié)果，生成下次移動(dòng)的隊(duì)列位置
                Integer r = rightMostIndexes.get(x);
                if (r == null) {
                    alignedAt = indexInText + 1;
                } else {
                    // 當(dāng)前壞字符串在模式串中存在，則將模式串最靠近好后綴的壞字符與母串的壞字符對(duì)齊，shift 實(shí)際為模式串總長(zhǎng)度
                    int shift = indexInText - (alignedAt + r);
                    alignedAt += shift > 0 ? shift : 1;
                }
                // 退出匹配
                break;
            } else if (indexInPattern == 0) {
                // 4.2 匹配到的話 并且最終匹配到模式串第一個(gè)字符，便是已經(jīng)找到匹配串，記錄下當(dāng)前的位置
                matches.add(alignedAt);
                alignedAt++;
            }
        }
    }
    return matches;
}

/**
 * 壞字符串
 * 依據(jù)待匹配的模式字符串生成一個(gè)壞字符串的移動(dòng)列，該移動(dòng)列中表明當(dāng)一個(gè)壞字符串出現(xiàn)時(shí)，需要移動(dòng)的位數(shù)
 */
private static Map<Character, Integer> preprocessForBadCharacterShift(String pattern) {
    Map<Character, Integer> map = new HashMap<>();
    for (int i = pattern.length() - 1; i >= 0; i--) {
        char c = pattern.charAt(i);
        if (!map.containsKey(c)) {
            map.put(c, i);
        }
    }
    return map;
}

參考：百度百科

Sunday

Daniel M.Sunday 于 1990 年提出的字符串模式匹配算法。其效率在匹配隨機(jī)的字符串時(shí)比其他匹配算法更快。平均時(shí)間復(fù)雜度為O(n)，最差情況的時(shí)間復(fù)雜度為O(n*m)。

原理

Sunday 算法跟 KMP 算法一樣，是從前往后匹配。在匹配失敗時(shí)，關(guān)注文本串中參加匹配的最末位字符的下一位字符，如果該字符不在模式串中，則整個(gè)模式串移動(dòng)到該字符之后。如果該字符在模式串中，將模式串右移使對(duì)應(yīng)的字符對(duì)齊。

Sunday算法和BM算法稍有不同的是，Sunday算法是從前往后匹配，在匹配失敗時(shí)關(guān)注的是主串中參加匹配的最末位字符的下一位字符。

• 如果該字符沒(méi)有在模式串中出現(xiàn)則直接跳過(guò)，即移動(dòng)位數(shù) = 模式串長(zhǎng)度 + 1；
• 否則，其移動(dòng)位數(shù) = 模式串長(zhǎng)度 - 該字符最右出現(xiàn)的位置(以0開(kāi)始) = 模式串中該字符最右出現(xiàn)的位置到尾部的距離 + 1。

舉例說(shuō)明Sunday算法。假定現(xiàn)在要在主串substring searching中查找模式串search：

• 剛開(kāi)始時(shí)，把模式串與文主串左邊對(duì)齊：
  
• 結(jié)果發(fā)現(xiàn)在第2個(gè)字符處發(fā)現(xiàn)不匹配，不匹配時(shí)關(guān)注主串中參加匹配的最末位字符的下一位字符，即標(biāo)粗的字符i，模式串search中并不存在i，模式串直接跳過(guò)一大片，向右移動(dòng)位數(shù) = 匹配串長(zhǎng)度 + 1 = 6 + 1 = 7，從 i 之后的那個(gè)字符（即字符n）開(kāi)始下一步的匹配：
  
• 結(jié)果第一個(gè)字符就不匹配，再看主串中參加匹配的最末位字符的下一位字符r，它出現(xiàn)在模式串中的倒數(shù)第3位，于是把模式串向右移動(dòng)3位（m - 3 = 6 - 3 = r 到模式串末尾的距離 + 1 = 2 + 1 =3），使兩個(gè)r對(duì)齊：
  
• 匹配成功。

Sunday算法的缺點(diǎn)：算法核心依賴于move數(shù)組，而move數(shù)組的值則取決于模式串，那么就可能存在模式串構(gòu)造出很差的move數(shù)組。

實(shí)現(xiàn)

/**
 * sunday 算法
 *
 * @param text    文本串
 * @param pattern 模式串
 * @return 匹配失敗返回-1，匹配成功返回文本串的索引(從0開(kāi)始)
 */
public static int sunday(char[] text, char[] pattern) {
    int tSize = text.length;
    int pSize = pattern.length;
    int[] move = new int[ASCII_SIZE];
    // 主串參與匹配最末位字符移動(dòng)到該位需要移動(dòng)的位數(shù)
    for (int i = 0; i < ASCII_SIZE; i++) {
        move[i] = pSize + 1;
    }
    for (int i = 0; i < pSize; i++) {
        move[pattern[i]] = pSize - i;
    }
    // 模式串頭部在字符串位置
    int s = 0;
    // 模式串已經(jīng)匹配的長(zhǎng)度
    int j;
    // 到達(dá)末尾之前
    while (s <= tSize - pSize) {
        j = 0;
        while (text[s + j] == pattern[j]) {
            j++;
            if (j >= pSize) {
                return s;
            }
        }
        s += move[text[s + pSize]];
    }
    return -1;
}

對(duì)比

僅做示例用，不同的算法在不同情況下表現(xiàn)不一致。與待搜索的字符串文本和模式匹配字符串有關(guān)。

public static void main(String[] args) {
    String text = "abcagfacjkackeac";
    String pattern = "ackeac";
    Stopwatch stopwatch = Stopwatch.createStarted();
    int bfRes = bf(text, pattern);
    stopwatch.stop();
    log.info("bf result:{}, take {}ns", bfRes, stopwatch.elapsed(TimeUnit.NANOSECONDS));

    stopwatch.reset();
    stopwatch.start();
    boolean kmpRes = kmpSearch(text, pattern);
    stopwatch.stop();
    log.info("kmp result:{}, take {}ns", kmpRes, stopwatch.elapsed(TimeUnit.NANOSECONDS));

    stopwatch.reset();
    stopwatch.start();
    List<Integer> bmMatch = bmMatch(text, pattern);
    stopwatch.stop();
    log.info("bmMatch result:{}, take {}ns", bmMatch, stopwatch.elapsed(TimeUnit.NANOSECONDS));

    stopwatch.reset();
    stopwatch.start();
    int sunday = sunday(text.toCharArray(), pattern.toCharArray());
    stopwatch.stop();
    log.info("sunday result:{}, take {}ns", sunday, stopwatch.elapsed(TimeUnit.NANOSECONDS));
}

某次輸出結(jié)果：

bf result:10, take 8833ns
kmp result:true, take 4541ns
bmMatch result:[10], take 90500ns
sunday result:10, take 5458ns

測(cè)試結(jié)果僅供參考。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-632466.html

參考

• 動(dòng)畫(huà)解釋KMP算法

到了這里，關(guān)于字符串查找匹配算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！