字符串匹配算法

假设主串（文本串）是一个长度为 \(n\) 的字符串 \(A\)，子串（模式串）是一个长度为 \(m\) 的字符串 \(B\)，我们的目的是要从 \(A\) 中匹配到 \(B\)

BF 算法

最朴素的串模式匹配算法

逻辑梳理

滑动窗口的做法

设主串（文本串） \(A\) 匹配到 \(i\) 位置，子串 \(B\) 匹配到 \(j\) 位置

如果 \(A[i]=B[j]\)，\(i++,j++\)，继续匹配下一个字符
如果 \(A[i]\ne B[j]\)，\(i=i-(j-1),j=0\)，也就是失配就回溯

代码实现

int BF(string A, string B){
    int n = A.size();
    int m = B.size();
    for(int i = 0; i <= n - m; ++i) {
        string temp = A.substr(i, m);
        if(temp == B) return i;
    }
    return -1;
}

int BF(string A, string B) {
    int n = A.size();
    int m = B.size();
    // 滑动窗口
    for(int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && A[i + j] == B[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

优点：不需要预处理，固定存储空间，算法复杂度 \(O(mn)\)

缺点：最坏复杂度高

KR 算法

将 \(m\) 个字符的比较变为一个哈希值的比较

算法效率取决于哈希函数的选取

定义哈希函数 \(f(s)=\Sigma_{i=1}^{n}\times k^{n-i}(\text{mod} p)\) 或者 \(f(s)=\Sigma_{i=1}^{n}\times k^{i}(\text{mod} p)\)

其中 \(k\) 为一个整数，\(p\) 为一个大整数

冷知识：实际使用时只取后几位的二进制的哈希函数

代码实现

int KR(string A, string B){
    int n = A.size();
    int m = B.size();
    
    int k = 256; // 基数
    int p = 1000000007; // 大质数
    long long B_hash = 0;
    for(int i = 0; i < m; ++i) B_hash = (B_hash * k + B[i]) % p;
    
    long long At_hash = 0;
    long long power = 1; // 用于存储 k^(m-1) mod p
    
    for(int i = 0; i < m; ++i){
        At_hash = (At_hash * k + A[i]) % p;
        if(i < m-1) power = (power * k) % p;
    }
    
    // 滑动窗口
    for(int i = 0; i <= n-m; ++i){
        if(B_hash == At_hash) return i;
        /*
        // 避免 hash 冲突
        if(B_hash == At_hash){
        	bool key = true;
        	for(int j = 0; j < m; ++j){
        		if(A[i+j] != B[j]){
        			key = false;
        			break;
        		}
        	}
        	if(key) return i;
        }
        */
        if(i < n-m){
            At_hash = (At_hash - A[i] * power % p + p) % p;
            At_hash = (At_hash * k + A[i+m]) % p;
        }
    }
    return -1;
}

KMP 算法

KMP 算法发现每个字符对应的该 \(k\) 值仅依赖于模式 \(B\) 本身，与目标对象 \(A\) 无关

逻辑梳理

设主串（文本串） \(A\) 匹配到 \(i\) 位置，子串 \(B\) 匹配到 \(j\) 位置

如果 \(j=-1\) 或者 \(A[i]=B[j]\)，\(i++,j++\)，继续匹配下一个字符
如果 \(j\ne -1\) 且 \(A[i]\ne B[j]\)，\(i\) 不变，\(j=next[j]\)
这一步相当于子串向右移动实际位数为 \(j-next[j](\ge 1)\)

前缀函数

长度为 \(n\) 的字符串 \(s\) 前缀函数为数组 \(next\)

其中 \(next[i]\) 定义为字串 \(s[0...i]\) 最长的相等的真前缀和真后缀的长度

即 \[next[i] = \max\{k=0...i}\\{k:s[0...k-1]=s[i-(k-1)...i]\}\]

规定 \(next[0]=-1\)

\(e.g.\)：字符串 \(abcabcd\)

\(next[4]=2\space\) \(abcab\) 最长相等的真前缀真后缀为 \(ab\)

\(next[5]=3\space\) \(abcabc\) 最长相等的真前缀真后缀为 \(abc\)

\(next[6]=0\space\) \(abcabcd\) 无相等的真前缀真后缀

计算前缀函数的方法

推导：如果第 \(i\) 位失配时，怎么求 \(next[i]\)

如果 \(A[i]==A[k]\) 显然 \(next[i+1] = k+1\)
如果 \(A[i]!=A[k]\)
由 \(next\) 数组的含义，我们知道 \(k = next[i]\)
\(p=A[0,..,k-1]\) 与 \(q=A[i-k,...i-1]\) 相等的，记此时 \(C=A[0,...i-1]\)
此时 \(p\) 的最长真前缀真后缀相等的字符串与 \(q\) 的最长真前缀真后缀相等的字符串相同，记这个字符串为 \(r\)
\(r\) 是 \(p\) 的真前缀，那么它是 \(C\) 的真前缀，\(r\) 是 \(q\) 的真后缀，那么它是 \(C\) 的真后缀
假如存在一个比 \(r\) 长的 \(C\) 的既是真前缀也是真后缀的字符串，记为 \(r'\)
那么 \(r'\) 是 \(p\) 的真前缀，\(q\) 的真后缀，由 \(p=q\) 知 \(r'\) 是 \(p\) 的真后缀，这与 \(r\) 的最大性矛盾，故 \(r\) 是 \(C\) 最长的相等的真前缀真后缀字符串
根据 \(next\) 数组的含义 \(next[i]=r.size()\)
容易知道 \(next[k]=r.size()\)，那么 \(k = next[i]=r.size()=next[k]\)
当 \(k == -1\) 时 \(next[++i]=0\)，和第一种情况合并

vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n-1){
        if(k == -1 || s[i] == s[k]) next[++i] == ++k;
        else k = next[k];
    }
    return next;
}

\(next\) 数组含义：

当前字符串中，最大长度相同真前缀和真后缀
发生失配时，下一步匹配时子串跳到的位置，如果 \(next[j]=k>0\)，则跳到子串的 \(k\) 位置\((next[j])\)

KMP 算法的多次匹配

如果要搜索的字符串匹配段有重叠的情况，匹配成功时，子串后移整个子串的最大公共真前缀和真后缀长度，和文本串的下一位继续匹配

代码实现

单次匹配

vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n+1);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n){
        while(k != -1 && s[i] != s[k]) k == next[k];
        ++i;++k;
        if(s[i] == s[k]) next[i] = next[k];
        else next[i] = k;
    }
    return next;
}

int KMP(string A, string B){
    int n = A.size();
    int m = B.size();
    vector<int> next = getNext(A);
    int i = 0,j = 0;
    while(i < n){
        while(j != -1 && A[i] != B[j]) j = next[j];
        ++i;++j;
        if(j >= m) return i - j;
    }
    return -1;
}

多次匹配

vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n+1);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n){
        while(k != -1 && s[i] != s[k]) k == next[k];
        ++i;++k;
        if(s[i] == s[k]) next[i] = next[k];
        else next[i] = k;
    }
    return next;
}

int KMP(string A, string B){
    int n = A.size();
    int m = B.size();
    vector<int> next = getNext(A);
    int i = 0, j = 0, ans = 0;
    while(i < n){
        while(j != -1 && A[i] != B[j]) j = next[j];
        ++i;++j;
        if(j >= m){
            ++ans;
            j = next[j];
        }
    }
    return ans;
}

预处理需要 \(O(m)\) 的时间和空间

算法时间复杂度 \(O(n+m)\)

查找阶段最大比较次数 \(2n-1\)

热知识：实际运用中 KMP 算法会比 BM 算法慢

冷知识：实际运用中 KMP 算法绝大多数情况会比 BF 算法慢

为 KMP 算法定制的字符数据中绝大多数情况会比 KR 算法慢

KMP 可以在 AC 自动机（KMP + Trie 树）中使用

BM算法

从右向左匹配字串

两大启发式规则：

坏字符规则：利用第一个不匹配的字符（坏字符）在子串中的位置信息，尝试进行大跨度跳跃，目标是对齐可能匹配的字符
好后缀规则：利用匹配成功的后缀的信息，尝试进行大跨度跳跃，目标是对齐可能匹配的后缀子串

逻辑梳理

从右向左比较模式串 \(B\) 和文本串 \(A\)，当发生失配时：

设文本串 \(A\) 中失配字符为 \(A[i]\)，模式串 \(B\) 中失配位置为 \(j\)（此时 \(B[j+1...m-1]\) 已匹配成功）

坏字符规则：在模式串 \(B[0...j-1]\) 中从右向左查找 \(A[i]\) 最后出现的位置 \(k\)

若找到，移动距离为 \(j-k\)
若未找到，移动距离为 \(j+1\)

好后缀规则：已匹配的后缀 \(t = B[j+1...m-1]\) 称为好后缀

若模式串中存在另一个与 \(t\) 相同的子串 \(t'\)（且 \(t'\) 左侧的字符与 \(t\) 左侧的字符不同），则将模式串滑动到 \(t'\) 与 \(t\) 对齐的位置
若不存在完整的 \(t'\)，则查找 \(t\) 的最长后缀是否是模式串的前缀，若是，则滑动到该前缀对齐位置
若都不满足，移动整个模式串长度

BM 算法取坏字符规则和好后缀规则中移动距离的较大值作为实际移动距离

最后出现位置表——BC 表

BC 表（Bad Character Table）记录字符表中每个字符在模式串中最后出现的位置

对于不在模式串中的字符，其值为 \(-1\)

vector<int> buildBC(string B){
    int m = B.size();
    vector<int> BC(256, -1);
    for(int i = 0; i < m; ++i){
        BC[(int)B[i]] = i;
    }
    return BC;
}

当失配时，坏字符移动量为 \(\max(1, j - BC[A[i]])\)

好后缀表——GS 表

GS 表（Good Suffix Table）用于好后缀规则的预处理

需要一个辅助数组 \(suffix[i]\)，表示以 \(B[i]\) 结尾的子串与模式串后缀的最长匹配长度

\[suffix[i] = \max\{k : B[i-k+1...i] = B[m-k...m-1]\}\]

vector<int> buildSuffix(string B){
    int m = B.size();
    vector<int> suffix(m, 0);
    suffix[m - 1] = m;
    int g = m - 1, f = 0;
    for(int i = m - 2; i >= 0; --i){
        if(i > g && suffix[i + m - 1 - f] < i - g){
            suffix[i] = suffix[i + m - 1 - f];
        } else {
            if(i < g) g = i;
            f = i;
            while(g >= 0 && B[g] == B[g + m - 1 - f]) --g;
            suffix[i] = f - g;
        }
    }
    return suffix;
}

利用 \(suffix\) 数组构建 GS 表

vector<int> buildGS(string B){
    int m = B.size();
    vector<int> suffix = buildSuffix(B);
    vector<int> GS(m, m);
    // 情况二：好后缀的后缀是模式串的前缀
    for(int i = m - 1; i >= 0; --i){
        if(suffix[i] == i + 1){
            for(int j = 0; j < m - 1 - i; ++j){
                if(GS[j] == m) GS[j] = m - 1 - i;
            }
        }
    }
    // 情况一：模式串中存在与好后缀匹配的子串
    for(int i = 0; i < m - 1; ++i){
        GS[m - 1 - suffix[i]] = m - 1 - i;
    }
    return GS;
}

代码实现

int BM(string A, string B){
    int n = A.size();
    int m = B.size();
    if(m == 0 || n < m) return -1;
    
    vector<int> BC = buildBC(B);
    vector<int> GS = buildGS(B);
    
    int i = 0;
    while(i <= n - m){
        int j = m - 1;
        while(j >= 0 && B[j] == A[i + j]) --j;
        if(j < 0) return i;
        i += max(GS[j], j - BC[(int)A[i + j]]);
    }
    return -1;
}

预处理需要 \(O(m+\Sigma)\) 的时间和空间，其中 \(\Sigma\) 为字符集大小

算法时间复杂度最坏为 \(O(m+n)\)（使用 Galil 规则），最好为 \(O(\frac{n}{m})\)

最好情况出现在文本串中每次比较的第一个字符都不在模式串中，每次跳 \(m\) 步

Galil 规则

Galil 规则是 BM 算法的一个优化，用于避免在已匹配区域中的重复比较

当一次成功的匹配或大范围移动后，模式串可能和文本串产生部分重叠的已匹配区域。Galil 规则记录上一次比较中已匹配的周期信息，在下一次比较中直接跳过这些已确认匹配的部分

设模式串的最小周期长度为 \(p\)（即 \(B[0...m-p-1] = B[p...m-1]\)），当发生完全匹配后，下一次比较只需从位置 \(m-p\) 开始向左比较到位置 \(0\) 即可跳过已知匹配部分

这使得 BM 算法在最坏情况下的比较次数从 \(O(mn)\) 降低到 \(O(n)\)，总时间复杂度为 \(O(m+n)\)

STL 中的字符串匹配算法

C++ 标准库中 std::string::find 和 std::search 的实现因编译器而异

GCC libstdc++：std::string::find 使用的是一种混合策略，对短模式串采用逐字符比较（类似 BF），对较长的模式串使用 Two-Way 算法（双向匹配算法）。std::search 同样使用了类似的策略

Two-Way 算法将模式串分为左右两部分，先匹配右半部分再匹配左半部分，时间复杂度 \(O(n+m)\)，空间复杂度 \(O(1)\)，是一个常数空间的线性时间算法

MSVC STL：std::string::find 采用的是朴素的 BF 算法，时间复杂度 \(O(mn)\)

LLVM libc++：std::string::find 也基本采用朴素匹配

总结：STL 中字符串匹配算法的性能不如手写的 KMP 或 BM 算法

此外，C++17 引入了 std::search 的重载版本，支持通过搜索器（Searcher）指定算法

#include <functional> // C++17
// Boyer-Moore 搜索器
auto it = std::search(A.begin(), A.end(),
    std::boyer_moore_searcher(B.begin(), B.end()));

// Boyer-Moore-Horspool 搜索器
auto it2 = std::search(A.begin(), A.end(),
    std::boyer_moore_horspool_searcher(B.begin(), B.end()));

Boyer-Moore-Horspool 是 BM 算法的简化版，只使用坏字符规则，省去了好后缀规则的预处理开销，在实际应用中往往比完整的 BM 算法更快

#字符串匹配算法

BF 算法

逻辑梳理

代码实现

KR 算法

代码实现

KMP 算法

逻辑梳理

前缀函数

KMP 算法的多次匹配

代码实现

BM算法

逻辑梳理

最后出现位置表——BC 表

好后缀表——GS 表

代码实现

Galil 规则

STL 中的字符串匹配算法

字符串匹配算法

同分类文章 5 related_posts_unit