朴素字符串匹配算法

这里假设text是一个文本，长度为n。pattern是需要匹配的子串，长度为m。

朴素字符串匹配算法，通过简单的循环，从头对比text中，每个长度为m的子串是否与pattern相等：

NaiveStringMatch.png

朴素字符串匹配算法实现十分简单，因为没有做任何预处理，时间复杂度为0((n-m+1)*m)：

/*
* @brief 朴素字符串匹配
* @return 返回pattern在text匹配成功的索引值，若未匹配成功，返回空数组
*/
vector<int> NaiveStringMatch(string text,string pattern) {
    vector<int> matched_index;
    int t_len = text.size();
    int p_len = pattern.size();

    if (t_len < p_len) {
        return matched_index;
    }
    for (int i = 0; i < t_len - p_len + 1; i++) {
        for (int j = 0; j < p_len; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
            if (j == p_len - 1) {
                matched_index.push_back(i);
            }
        }
    }
    return matched_index;
}

Rabin-Karp 算法

为了方便理解， 在这里先假设，T为长度n的文本，P为长度m的模式，T、P只包含0-9的数字字符。因此，可以简单的将P字面的值，作为P的值。

例如： P= "123" , 这时候P的值就是123。

设p为P[1 : m]的值，Ts 为T[s : s + m - 1]的值，当p == Ts 时，可知字符串匹配成功。

相比朴素字符串匹配算法，如果，能够通过Ts的值，直接计算出Ts+1的值，就可以跳过子串对比的过程。

假设 T = ”123456“ ， m = 3。 则有T0 = 123，T1 = 234。 T1相对于T0去除了一个高位1，增加了一个低位4

由上可推出 Ts+1 =10 * (Ts - T[s] * 10^(m-1)) + T[s+1]

现在的问题是，当m太大，上面对于Ts+1的计算，就不可能在常数时间内完成。

这里就需要,找到一个合适的q,运用模运算,得到：

Ts+1 = (10 * (Ts - T[s] * h) + T[s+1] ) mod q
h = 10^(m - 1) mod q

运用模运算,可能会出现，T[s : s + m - 1] ！= P[1 : m]，但是Ts == p 的情况。因此当Ts == p时，需要再次判断T[s : s + m - 1] 和 P[1 : m] 是否相等。

如下图，P = ”31415“，q为质数13，通过计算p = 7：

Rabin-Karp.png

为推广到任意字符匹配，我们可以将底10换成其他数值

Ts+1 = (d * (Ts - T[s] * h) + T[s+1] ) mod q
h = d^(m - 1) mod q

例如：ASCII字符最大值为128，我们使 d = 128，可以进行ASCII字符的匹配。

c++代码实现如下：

/*
* @brief Rabin-Karp 匹配算法
* @return 返回pattern在text匹配成功的索引值，若未匹配成功，返回空数组
*/
vector<int> RabinKarpMatch(string text, string pattern) {
    
    vector<int> matched_index;
    int t_len = text.size();
    int p_len = pattern.size();
    
    /* 以128为底，匹配所有ASCII码字符 质数选择： 113 */
    int d = 128;
    int q = 113;
    int h = pow(d, p_len - 1);
    h = fmod(h,113);

    int t_hash = 0;
    int p_hash = 0;
    for (int i = 0; i < p_len; i++) {
        p_hash = fmod((d * p_hash + pattern[i]) , q);
        t_hash = fmod((d * t_hash + pattern[i]), q);
    }
    cout << "p_hash: "<< p_hash << endl;
    for (int i = 0; i < t_len - p_len + 1; i++) {
        cout <<i<<".t_hash:" << t_hash << endl;
        if (t_hash == p_hash) {
            for (int j = 0; j < p_len; j++) {
                if (text[i + j] != pattern[j]) {
                    break;
                }
                if (j == p_len - 1) {
                    matched_index.push_back(i);
                }
            }
        }

        if (i < t_len - p_len) {
            t_hash = fmod((d * (t_hash - text[i] * h) + text[i + p_len]) , q);
            while (t_hash < 0) {
                t_hash += q;
            }
        }
    }
    return matched_index;
}

KMP算法

这里引入一些概念：

1. 字符串的前缀：符号串左部的任意子串（或者说是字符串的任意首部）

2. 字符串的后缀：符号串右部的任意子串（或者说是字符串的任意尾部）

kmp.png

c++代码实现：

static vector<int> KmpPrefixComputing(string pattern) {
    vector<int> prefix(pattern.size(), 0);

    /* pattern中已匹配字符数 */
    int k = 0; 
    prefix[0] = k;

    /* 本质是由pattern[0:] 取匹配 pattern[1:] 求pattern[0:i]后缀的关于pattern的最长前缀 */
    for (int i = 1; i < pattern.size(); i++) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = prefix[k - 1];
        }
        if (pattern[k] == pattern[i]) {
            k++;
        }
        prefix[i] = k;
    }
    return prefix;
}

/*
* @brief KMP 匹配算法
* @return 返回pattern在text匹配成功的索引值，若未匹配成功，返回空数组
*/
vector<int> KmpMatch(string text, string pattern) {
    vector<int> matched_index;
    vector<int> prefix = KmpPrefixComputing(pattern);

    int k = 0;
    for (int i = 0; i < text.size(); i++) {
        while (k > 0 && pattern[k] != text[i]) {
            k = prefix[k - 1];
        }
        if (pattern[k] == text[i]) {
            k++;
        }
        if (k == pattern.size()) {
            matched_index.push_back(i - pattern.size() + 1);
            k = prefix[k];
        }
    }
    return matched_index;
}