字符串匹配算法很典型。其中涉及的AC自動(dòng)機(jī)，進(jìn)制表示預(yù)處理以及大整數(shù)的模運(yùn)算等等思想，對(duì)算法設(shè)計(jì)很有借鑒意義。

基本問(wèn)題，一個(gè)字符集 S[1, ..., n] 中，確定子字符串 P[1,..., m] 首次出現(xiàn)的位置。如 iloveyou中找到 ey，

這個(gè)結(jié)果可能是1到 n - m ，當(dāng)然如果查找失敗，結(jié)果可已返回一個(gè)負(fù)數(shù)-1。

樸素的算法

用模式P[1,m]去匹配 S[1, m], 失敗后將S的標(biāo)往右移動(dòng)一格，匹配 S[2, m + 1],... ，最后比較的子串是 S[n - m, n]
這個(gè)算法最壞情況是比較 n - m + 1 次，每次最壞的情況是比較 m 次字符。
這樣，它的時(shí)間復(fù)雜度是

改進(jìn)版本的做法是，移動(dòng)下標(biāo)的時(shí)候盡量跳的遠(yuǎn)一點(diǎn)，如何做到這一點(diǎn)？我們要充分利用上一次匹配殘留的信息。

int match(const char *str, const char *p)
{
    if (str == NULL || p == NULL)
        return -1;
    int m, n, i, j;
    n = strlen(str);
    m = strlen(p);

    for (i = 0; i < n - m; ++i) {
        for (j = m - 1; j >= 0; --j) {
            if (*(p + j) != *(str + i + j)) {
                printf("%c, %c", *(str + j), *(p + j));
                break;
            }
        }
        if (j < 0) { // match succuss
            return i;
        }
    }
    return -1;
}

• 模式P的構(gòu)成
• 上一次匹配失敗的位置

舉個(gè)例子如果我們?cè)? iloveyou 中 找 ey

• step1 比較 il 和ey ， 這兩個(gè)子串完全不同，下一個(gè)子串 lo 肯定不能配對(duì)，因?yàn)橐阎男畔⑽覀円呀?jīng)知道 lo 至少含有一個(gè) ey 沒(méi)有的串——所以其實(shí)我們可以直接跳2格(2 = size(ey))
• step2 比較 ov 和 ey
• step3 繼續(xù)根據(jù)step1 的分析，跳2個(gè)位置到 ey 查到目標(biāo)
  這里比較的次數(shù)是 2 + 2 + 2 = 6次
  使用樸素算法 需要 5 * 2 = 10次

實(shí)際上，如果 模式 P 的字符都是兩兩不同，理論上可以用 的復(fù)雜度優(yōu)化算法

改進(jìn)版本

int impr_match(const char *str, const char *p)
{
    /*
     * 只能用于 p 字符互不相同的情況
     */
    if (str == NULL || p == NULL)
        return -1;
    int m, n, i, j;
    n = strlen(str);
    m = strlen(p);

    int h[256]; // hash table ;記錄模式每個(gè)字符出現(xiàn)的位置
    memset(h, 0, sizeof(h));

    for (i = 0; i < m; ++i) {
        h[p[i] - ' '] = i + 1; // 空格 32
    }

    for (i = 0; i < n - m;) {
        for (j = m - 1; j >= 0; --j) {
            if (*(p + j) != *(str + i + j)) {
                break;
            }
        }
        if (j < 0) { // match succuss
            return i;
        }
        if (h[*(str + i + j) - ' '] > 0) { // appeared
            i += (m - h[*(str + i + j) - ' ']);
        } else {
            i += m;
        }
    }
    return -1;
}

模式 P 有重復(fù)字符的改進(jìn)版本，可以在掃描 s 串的時(shí)候判定字符是否在 P 中出現(xiàn)過(guò)，沒(méi)有出現(xiàn)則可以斷定，這個(gè)包含這個(gè)字符的子串都不可能匹配，可一跳 m，其余情況則按照樸素的算法逐步移動(dòng) m 個(gè)位置

Rabin-Karp算法

這個(gè)算法是典型的實(shí)用性比較強(qiáng)，但是理論上并沒(méi)有比樸素的匹配算法強(qiáng)大的一個(gè)算法。

它常規(guī)情況下的文本及模式，具有很好的平均性能 （如果模式長(zhǎng)度 m 比n 小的話）

Rabin-Karp算法的關(guān)鍵之處——利用了大整數(shù)的模p同余的性質(zhì)——
來(lái)看兩個(gè)大整數(shù) 素?cái)?shù)
有以下的性質(zhì)

• 如果
• 如果 則未必有

我們用同余運(yùn)算去檢測(cè) S的子串是否和模式P相同時(shí)，通過(guò)先探測(cè)余數(shù)的方法感知一下，如果同余，則繼續(xù)用樸素的逐字符比較的方法判定二者是否一致。

同余但仍然不同的情況，稱之為偽命中，如果偽命中很多，多到跟 n - m 差不多，那么意味著我們做同余模運(yùn)算是多此一舉，浪費(fèi)表情。

但是實(shí)際情況沒(méi)有那么糟糕，一般來(lái)說(shuō)，偽命中的數(shù)量很小，這就導(dǎo)致我們做模數(shù)運(yùn)算的收益很大。

回過(guò)頭來(lái)要考慮的問(wèn)題是——怎么做預(yù)處理將字符轉(zhuǎn)變成可以進(jìn)行模運(yùn)算的“數(shù)字”？

答案是進(jìn)制化。

字符集總量總是有限的，我們可以創(chuàng)造一個(gè)和字符集那么大的進(jìn)制 d，然后把一串字符當(dāng)成一個(gè)數(shù)字，選擇一個(gè)和模式相比小一些的素?cái)?shù)——素?cái)?shù)的素性和進(jìn)制是沒(méi)什么關(guān)系的，把5寫(xiě)成3進(jìn)制，2進(jìn)制，它仍然是一個(gè)素?cái)?shù)

舉個(gè)例子，如果字符集是10個(gè)，bingo，我們恰好可以用10進(jìn)制來(lái)完成此事，但通?？傋址际巧先f(wàn)個(gè)，特別是漢字 ，以及Unicode字符集，Unicode可表示的字符空間大約是 110萬(wàn)，現(xiàn)行已賦字符大約17萬(wàn)。如果我們要在一個(gè)充滿 Unicode字符的文本中匹配，使用Rabin-Karp算法是否意味著需要?jiǎng)?chuàng)建 十萬(wàn)計(jì)進(jìn)制的運(yùn)算？

是的。但不是必須，有一種叫做滾動(dòng)哈希的方法可以完成等價(jià)的事情。

看十進(jìn)制的例子

取
那么 模運(yùn)算可以逐步進(jìn)行

把右側(cè)每一項(xiàng)模11取余，得到
再加起來(lái)得到 32
于是

最小正剩余就是10， 和直接計(jì)算的結(jié)果一樣

滾動(dòng)哈希的代碼

pattern_hash = 0
for x in pattern_codepoints:
    pattern_hash = (pattern_hash * B + x) % M

再以 314159為例 ，逐步看滾動(dòng)哈希的計(jì)算過(guò)程 ，p = 11

• step1 讀入3， 3 模11 余3
• step2 讀入1 ，(3 * 10^1 + 1 ) 模 11 余 9
• step3 讀入4，此時(shí)不要用31 乘基數(shù)10，而是 用9, 90 + 4=94 模11余6
• step4 讀入1， 6 * 10 + 1 模11余 6
• step5 讀入5， 6 * 10 + 5 模11 余10
• step6 讀入9， 10 * 10 + 9 模11 余10

End
滾動(dòng)求值的好處顯而易見(jiàn)——沒(méi)有裝入太龐大的數(shù)，內(nèi)存毫無(wú)壓力，計(jì)算快，復(fù)雜和被取模的字符串長(zhǎng)度一樣。