int search(const string &T, const string&P) {
    if (P.empty()) { // 模式串为空，匹配任意字符串
        return 0;
    // i<=T.size()-P.size() 是为了 T[i+j] 不越界
    for (size_t i = 0; i <= T.size() - P.size(); ++i) {
        for (size_t j = 0; j < P.size(); ++j) {
            if (T[i + j] != P[j]) {
                break;
            if (j == P.size() - 1) {
                return i;
    return -1; // -1 表示没有匹配
这个算法的缺点是整数可能溢出。解决办法是使用其它哈希方法，例如将字符串哈希为每个字符的和，但这会造成哈希值冲突，为了解决冲突，需要在哈希值匹配之后，对字符串逐一比较。如果存在大量哈希冲突，每次都要再对比字串，因此这样的方法最差时间复杂度是
\(O(nm)\) 。实际上除非模式串较大，否则遇到哈希冲突的情况是非常少的。受到
Bloom-filter 算法的启发，我曾同时使用 8 个不同的哈希函数计算匹配哈希值，模式串不长所以基本不会冲突，速度很快。缺点就是总被人问“你搞的什么鬼”。后来有人改成了KMP
算法，业务上线2年后发现写错了，review 名单里面也有我， 尴尬的很。写错的算法还不如暴力求解。
第2轮匹配时，模式串 \(d\) 对应对应主串的 \(a\) ，不匹配，右移1字节。如果知道 \(a\) 在模式串中最后出现的位置是 0, 那么直接后移2字节，让主串的 \(a\) 直接与模式串的 \(a\)
对正，可以节省很多时间。
vector<int> generate_bad_char(string P) {
    vector<int> bc(kMaxChar);
    fill(bc.begin(), bc.end(), -1); // 初始化
    for (int i = 0; i < P.size(); ++i) {
        bc[P[i]] = i;
    return bc;
// 好后缀
void generate_good_suffix(string P, vector<int>&suffix, vector<bool>&prefix) {
    suffix = vector<int>(P.size());
    prefix = vector<bool>(P.size());
    fill(prefix.begin(), prefix.end(), false);
    fill(suffix.begin(), suffix.end(), -1);
    // P[0..i] ~=? P[...P.size()-1]
    for (int i = 0; i < P.size() - 1; ++i) {
        int j = i;
        int k = 0; // 公共后缀子串的长度
        while (j >= 0 && P[j] == P[P.size() - 1 - k]) {
            // P[j..i] 与 P[...P.size()-1] 匹配
            --j; ++k;
            suffix[k] = j + 1;
        if (j == -1) { // 后缀与前缀匹配 P[0..i] = P[...P.size()-1]
            prefix[k] = true;
// j 表示坏字符对应 P 的下标
// m 表示 P.size()
int move_gs(int j, int m, vector<int>suffix, vector<bool>prefix) {
    int k = m - 1 - j; // 好后缀长度
    if (suffix[k] != -1) { // P 中存在其他好后缀匹配
        return j - suffix[k] + 1;
    for (int r = j + 2; r <= m - 1; ++r) {
        // 查找最长匹配的前缀
        if (prefix[m - r]) {
            return r;
        return r;
    // 都没匹配，就直接右移整串
    return m;
int bm(string T, string P) {
    if (P.empty()) { // 模式串为空，匹配任意字符串
        return 0;
    if (P.size() > T.size()) { // 模式串比主串还大，肯定不匹配
        return -1; // 不匹配返回 -1
    auto bc = generate_bad_char(P);
    vector<int> suffix;
    vector<bool> prefix;
    generate_good_suffix(P, suffix, prefix);
    int i = 0; // 匹配位置
    while (i <= T.size() - P.size()) {
        int j;
        for (j = P.size()-1; j >= 0; --j) { // 模式串从后往前 P[j] .. P[0]
            if (T[i+j] != P[j]) {
                break; // 找到坏字符 T[i+j]
        if (j < 0) {
            return i; // 没有坏字符，匹配成功
        int x = j - bc[T[i+j]]; // 坏字符是 T[i+j]
        int y = 0;
        if (j < P.size() - 1) { // 存在好后缀
            y = move_gs(j, P.size(), suffix, prefix);
        i += max(x, y);
    return -1;
\(next[i]=k\) 等价于 \(P[0..k]=P[i-k..i]\) 。此时若 \(P[k+1]=P[i+1]\) , 那么
\(P[0..k+1]=P[i-k..i+1]\) , 即 \(next[i+1]=k+1\) 。
若 \(P[k+1]\neq P[i+1]\) ，就要尝试更短长度的前缀后缀匹配。令 \(m=next[k]\) ，
\(P[0..m]=P[i-m..i]\) 。若 \(P[m+1]=P[i+1]\) ，那么 \(next[i+1]=m+1\) 。以此类推。
实现如下：