字符串匹配算法: kmp和bm算法

abcacabdc
abd
   abd

abcacabdc
   abd
     abd

   v  __
abcacabcbcbacabc
 abbccbc
    abbccbc
      -- --

// 字符集大小
const static int kMaxChar = 256; 
// 坏字符
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 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 数组 (nextval)
vector<int> gen_nextval(const string& P) {
    // 1. 先计算标准的 next 数组
    vector<int> next(P.size());
    if (P.empty()) return next;

    next[0] = -1;
    int k = -1;
    for (int i = 1; i < P.size(); ++i) {
        while (k != -1 && P[k + 1] != P[i]) {
            k = next[k];
        }
        if (P[k + 1] == P[i]) {
            ++k;
        }
        next[i] = k;
    }

    // 2. 基于 next 数组计算 nextval
    // 逻辑：如果 P[i+1] == P[next[i]+1]，则说明回退后遇到的字符和当前一样，
    // 肯定还是不匹配，所以可以直接继续回退。
    vector<int> nextval = next;
    for (int i = 0; i < P.size(); ++i) {
        if (i + 1 < P.size()) {
            int j = next[i]; // j 是 P[0..i] 的最长公共前缀后缀的末尾下标
            // 如果回退后的下一个字符 P[j+1] 与当前失配字符 P[i+1] 相同
            if (j != -1 && P[i + 1] == P[j + 1]) {
                // 递归优化：直接指向 nextval[j]
                // 注意：因为是从前往后遍历，nextval[j] 此时已经是优化过的值了
                nextval[i] = nextval[j];
            }
        }
    }
    return nextval;
}

int kmp_optimized(const string& T, const string& P) {
    if (P.empty()) return 0;
    if (P.size() > T.size()) return -1;

    auto nextval = gen_nextval(P);
    int j = 0;
    for (int i = 0; i < T.size(); ++i) {
        // 使用 nextval 数组进行跳转，逻辑与标准 KMP 完全一致
        while (j > 0 && T[i] != P[j]) {
            j = nextval[j - 1] + 1;
        }
        if (T[i] == P[j]) {
            ++j;
        }
        if (j == P.size()) {
            return i - P.size() + 1;
        }
    }
    return -1;
}