字符串匹配算法

KMP算法

Knuth–Morris–Pratt 算法（KMP算法） 用来判断一个模式字符串是否是主字符串的子串。

如果用最简单粗暴的方式解决这个字符串匹配问题，会怎么做？例如，判断ABABD是不是ABABCABABABD的子串？

从最开始扫描，ABABD 和 ABABC 直到第5(index=4)个字符不匹配，BABCA在第一个字符就不匹配，直到扫描到ABABD，结束。

bool is_match(const std::string &pat, const std::string &main) {
  if (pat.size() > main.size())
    return false;
  int i, j;
  for (i = 0; i <= main.size() - pat.size(); i++) {
    for (j = 0; j < pat.size(); j++) {
      if (main[i + j] != pat[j]) {
        break;
      }
    }
    if (j == pat.size()) {
      return true;
    }
  }
  return false;
}

但是这在事实上遗漏了很多有用的信息，当我们将ABABD和ABABC比较之后，我们其实已经知道了BABC?不可能再和ABABD匹配了，同理ABC??，BC???。那么我们究竟可以往下直接跳多少？这就是KMP算法的精髓，当匹配失败时，利用已经部分匹配的信息，避免重新检查已知匹配的字符。

Partial Match Table

部分匹配表，也叫失败函数、next数组。next[i]表示：对于模式串pat[0...i]，其真前缀和真后缀的最长公共部分的长度。

真前缀：不包含最后一个字符的所有前缀
真后缀：不包含第一个字符的所有后缀

例如，对于模式串"ABABD"：

next[0] = 0（规定，没有真前缀和真后缀可比较）
next[1] = 0（"AB"的真前缀是"A"，真后缀是"B"，无公共部分）
next[2] = 1（"ABA"的真前缀有"A","AB"，真后缀有"A","BA"，最长公共部分是"A"，长度为1）
next[3] = 2（"ABAB"的真前缀有"A","AB","ABA"，真后缀有"B","AB","BAB"，最长公共部分是"AB"，长度为2）
next[4] = 0（"ABABD"的真前缀与真后缀没有公共部分）

那么next数组有什么用呢？回到上面的例子，当我们将ABABD和ABABC比较之后，发现在index=4的地方不匹配了，（我们只利用了C!=D这个信息），我们知道BAB??（移动1个）是肯定不匹配的，但是AB???（移动2个）是可能匹配的，也就是说ABAB的真前缀和真后缀的最长公共匹配部分是AB，所以我们移动2个。

Implementation

求解next数组的方式：

void computeNext(const string& pattern, vector<int>& next) {
    int m = pattern.length();
    next[0] = 0;  // 初始值

    for (int i = 1, j = 0; i < m; i++) {
        // 如果当前字符不匹配，回退j
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }

        // 如果当前字符匹配，j增加
        if (pattern[i] == pattern[j]) {
            j++;
        }

        next[i] = j;  // 设置next值
    }
}

完整的KMP算法

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> positions;
    int n = text.length();
    int m = pattern.length();

    if (m == 0) return positions;

    // 计算next数组
    vector<int> next(m, 0);
    computeNext(pattern, next);

    // 进行匹配
    for (int i = 0, j = 0; i < n; i++) {
        // 不匹配时，利用next回退
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }

        // 匹配时，j前进
        if (text[i] == pattern[j]) {
            j++;
        }

        // 完全匹配
        if (j == m) {
            positions.push_back(i - m + 1);  // 记录匹配位置
            j = next[j - 1];  // 继续寻找下一个匹配
        }
    }

    return positions;
}

KMP算法的时间复杂度是\(O(|main|+|pat|)\)

Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串搜索算法，由Robert S. Boyer和J Strother Moore于1977年发明。它被认为是实际应用中最快的字符串搜索算法之一，特别是对于长文本和长模式串。相比KMP算法，Boyer-Moore算法在很多情况下表现更优，尤其是在自然语言文本处理中。

BM算法的最坏时间复杂度也是\(O(|main|)\)，平均时间复杂度为\(O(|main|/|pat|)\)。

C++17的标准库中可以直接使用这个算法std::search，参考std::search - cppreference.com。

Sunday算法

Sunday 算法 是 Boyer-Moore 的简化版，实现更简单，适合短模式串。