字符串匹配算法(一)

字符串匹配算法很典型。其中涉及的AC自动机，进制表示预处理以及大整数的模运算等等思想，对算法设计很有借鉴意义。

基本问题，一个字符集 S[1, ..., n] 中，确定子字符串 P[1,..., m] 首次出现的位置。如 iloveyou中找到 ey，

这个结果可能是1到 n - m ，当然如果查找失败，结果可已返回一个负数-1。

朴素的算法

用模式P[1,m]去匹配 S[1, m], 失败后将S的标往右移动一格，匹配 S[2, m + 1],... ，最后比较的子串是 S[n - m, n]
这个算法最坏情况是比较 n - m + 1 次，每次最坏的情况是比较 m 次字符。
这样，它的时间复杂度是 $\Theta (m(n - m + 1))$

改进版本的做法是，移动下标的时候尽量跳的远一点，如何做到这一点？我们要充分利用上一次匹配残留的信息。

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的构成
上一次匹配失败的位置

举个例子如果我们在 iloveyou 中找 ey

step1 比较 il 和ey ，这两个子串完全不同，下一个子串 lo 肯定不能配对，因为已知的信息我们已经知道 lo 至少含有一个 ey 没有的串——所以其实我们可以直接跳2格(2 = size(ey))
step2 比较 ov 和 ey
step3 继续根据step1 的分析，跳2个位置到 ey 查到目标
这里比较的次数是 2 + 2 + 2 = 6次
使用朴素算法需要 5 * 2 = 10次

实际上，如果模式 P 的字符都是两两不同，理论上可以用 $\Theta(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 ;记录模式每个字符出现的位置
    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 有重复字符的改进版本，可以在扫描 s 串的时候判定字符是否在 P 中出现过，没有出现则可以断定，这个包含这个字符的子串都不可能匹配，可一跳 m，其余情况则按照朴素的算法逐步移动 m 个位置

Rabin-Karp算法

这个算法是典型的实用性比较强，但是理论上并没有比朴素的匹配算法强大的一个算法。

它常规情况下的文本及模式，具有很好的平均性能 $\Theta(n)$ （如果模式长度 m 比n 小的话）

Rabin-Karp算法的关键之处——利用了大整数的模p同余的性质——
来看两个大整数 $a, b$ 素数 $p$
有以下的性质

如果 $a \ne b, 那么 a \not\equiv b\pmod{p}$
如果 $a \equiv b\pmod{p}$ 则未必有 $a = b$

我们用同余运算去检测 S的子串是否和模式P相同时，通过先探测余数的方法感知一下，如果同余，则继续用朴素的逐字符比较的方法判定二者是否一致。

同余但仍然不同的情况，称之为伪命中，如果伪命中很多，多到跟 n - m 差不多，那么意味着我们做同余模运算是多此一举，浪费表情。

但是实际情况没有那么糟糕，一般来说，伪命中的数量很小，这就导致我们做模数运算的收益很大。

回过头来要考虑的问题是——怎么做预处理将字符转变成可以进行模运算的“数字”？

答案是进制化。

字符集总量总是有限的，我们可以创造一个和字符集那么大的进制 d，然后把一串字符当成一个数字，选择一个和模式相比小一些的素数——素数的素性和进制是没什么关系的，把5写成3进制，2进制，它仍然是一个素数

举个例子，如果字符集是10个，bingo，我们恰好可以用10进制来完成此事，但通常总字符集都是上万个，特别是汉字，以及Unicode字符集，Unicode可表示的字符空间大约是 110万，现行已赋字符大约17万。如果我们要在一个充满 Unicode字符的文本中匹配，使用Rabin-Karp算法是否意味着需要创建十万计进制的运算？

是的。但不是必须，有一种叫做滚动哈希的方法可以完成等价的事情。

看十进制的例子

$314159 = 3 ·10^5 + 1 ·10^4 + 4·10^3 + 1·10^2 + 5·10 + 9$
取 $p = 11$
那么模运算可以逐步进行
$314159 \equiv (3 ·10^5 + 1 ·10^4 + 4·10^3 + 1·10^2 + 5·10 + 9 ) \pmod p$
把右侧每一项模11取余，得到 $8, 1, 7, 1, 6, 9$
再加起来得到 32
于是 $314159 \equiv 32 \pmod {11}$

最小正剩余就是10，和直接计算的结果一样

滚动哈希的代码

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

再以 314159为例，逐步看滚动哈希的计算过程，p = 11

step1 读入3， 3 模11 余3
step2 读入1 ，(3 * 10^1 + 1 ) 模 11 余 9
step3 读入4，此时不要用31 乘基数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
滚动求值的好处显而易见——没有装入太庞大的数，内存毫无压力，计算快，复杂和被取模的字符串长度一样。

字符串匹配算法(一)