字符串匹配与 KMP 算法

Ricky_Theseus

112人浏览 · 2026-07-06 13:03:26

Ricky_Theseus · 2026-07-06 13:03:26 发布

字符串匹配与 KMP 算法

一、直观类比：查字典

你在翻一本厚字典，要找「KMP」这个词。你不会每次从第一个字开始比——假如你翻到了「KM」开头的区域，发现后面跟的是「A」而不是「P」，你会直接跳到「KN」区域，而不是退回到「K」重新翻。

KMP 做的正是这件事：当模式串在某位置失配时，利用已经匹配过的信息，跳过那些必然不可能成功的起始位置，让文本指针不回溯。

二、暴力匹配（Brute-Force）

最直观的做法：用模式串对齐文本的每一个起始位置，逐字符比较。

#include <string>
#include <vector>

std::vector<int> bruteForce(const std::string& text, const std::string& pattern) {
    std::vector<int> matches;
    int n = text.size(), m = pattern.size();
    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) ++j;
        if (j == m) matches.push_back(i);
    }
    return matches;
}

复杂度：O(nm)。最坏情况 text = "AAAAA...AB"，pattern = "AAAAB"，每一轮几乎比到最后一个字符才失配，效率极低。

问题在哪：失配时 i 只前进 1，之前比过的字符全白费了。KMP 要解决的正是这个「回溯浪费」。

三、KMP 核心思想

KMP（Knuth–Morris–Pratt）将匹配拆成两个阶段：

预处理：对模式串计算 next 数组
匹配：文本指针 i 从不回溯，模式串指针 j 按 next 跳转

3.1 next 数组定义

next[i] = 模式串 [0 : i] 这个子串中，最长相等前后缀的长度。

前缀：不含最后一个字符的头部子串
后缀：不含第一个字符的尾部子串

例如 "ABAB"：

前缀集合：{"A", "AB", "ABA"}
后缀集合：{"B", "AB", "BAB"}
最长公共前后缀："AB"，长度 2

所以 next[3] = 2（下标从 0 算）。

3.2 next 数组构造 — 双指针递推

用两个指针：j（前缀指针） 和 i（后缀指针）。

j 指向当前最长相等前缀的末尾（也是已匹配长度）
i 从 1 开始遍历模式串，始终是后缀的末尾

规则：

pattern[i] == pattern[j] → ++j; next[i] = j; ++i;
不相等且 j > 0 → j = next[j - 1]（跳回去）
不相等且 j == 0 → next[i] = 0; ++i;

这个「跳回去」是 KMP 最精妙的地方：当后缀末尾和前缀末尾不匹配时，我们用已经算好的 next 值，把前缀指针缩短到仍然可能匹配的位置，避免从头开始试。

```mermaid
graph TD
    A["开始：j=0, i=1"] --> B{"pattern[i] == pattern[j]?"}
    B -->|"相等"| C["next[i] = ++j
i++"]
    B -->|"不相等"| D{"j > 0 ?"}
    D -->|"是"| E["j = next[j-1]
// 跳回"]
    D -->|"否"| F["next[i] = 0
i++"]
    E --> B
    C --> G{"i < m?"}
    F --> G
    G -->|"是"| B
    G -->|"否"| H["构造完成"]
style A fill:#e3f2fd,stroke:#1565c0
style B fill:#fff3e0,stroke:#e65100
style E fill:#ffebee,stroke:#c62828
style H fill:#e8f5e9,stroke:#2e7d32

</pre>
</center>

---

## 四、完整 C++ 实现

```cpp
#include <iostream>
#include <string>
#include <vector>

std::vector<int> getNext(const std::string& pattern) {
    int m = pattern.size();
    std::vector<int> next(m, 0);
    int j = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        next[i] = j;
    }
    return next;
}

std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> matches;
    if (pattern.empty()) return matches;
    std::vector<int> next = getNext(pattern);
    int n = text.size(), m = pattern.size();
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            matches.push_back(i - m + 1);
            j = next[j - 1];
        }
    }
    return matches;
}

// 测试
int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    std::vector<int> res = kmpSearch(text, pattern);
    std::cout << "匹配位置: ";
    for (int pos : res) std::cout << pos << " ";
    std::cout << "\n";  // 输出: 10
    return 0;
}

匹配过程示意

```mermaid
graph LR
    T["文本: A B A B D A B A ..."] --> M1["i=4 失配
j=3→next[2]=1"]
    M1 --> M2["j=1 对齐继续
text[4]=D ≠ pattern[1]=B"]
    M2 --> M3["j→next[0]=0
i++"]
    M3 --> M4["i=10 匹配成功
j=9→next[8]=4"]
style T fill:#e8eaf6,stroke:#283593
style M1 fill:#fff3e0,stroke:#e65100
style M4 fill:#e8f5e9,stroke:#2e7d32

</pre>
</center>

文本指针 i 从 0 走到 n-1，**永不回溯**。失配时只动 j，而 j 借助 next 数组一跳就是安全的距离。

---

## 五、复杂度分析

| 阶段 | 时间 | 空间 |
|------|------|------|
| 构造 next | O(m) | O(m) |
| 匹配 | O(n) | O(1) |
| **合计** | **O(n + m)** | **O(m)** |

- 构造时每个字符最多被 j 回退一次，均摊 O(1)
- 匹配时 i 只前移，j 的回退总数 ≤ n，均摊 O(1)

对比暴力 O(nm)，在长文本上差距巨大。m = 1000, n = 10^6 时，暴力最坏 10^9 次比较，KMP ≈ 10^6 次。

---

## 六、扩展对比

### BM 算法（Boyer-Moore）

从右向左匹配，利用两类启发规则——**坏字符**（失配字符决定跳多远）和**好后缀**（已匹配后缀决定跳多远）。实践中 BM 比 KMP 快 3–5 倍，尤其适合大字符集（如英文文本）。但预处理更复杂，小模式串下优势不明显。

### Rabin-Karp 算法

用滚动哈希（如 Rabin fingerprint）将字符串比较转化为 O(1) 的哈希比较。平均 O(n + m)，最坏 O(nm)（哈希冲突时退化）。**适合多模式匹配**——一次遍历文本，同时查找多个模式串。

| 算法 | 预处理 | 匹配 | 特点 |
|------|--------|------|------|
| 暴力 | O(1) | O(nm) | 实现简单，最坏慢 |
| KMP | O(m) | O(n) | 文本指针不回溯，理论最优 |
| BM | O(m + σ) | O(n) 平均 | 工程最快的单模式算法 |
| Rabin-Karp | O(m) | O(n) 平均 | 适合多模式 |

---

## 七、面试题

### 7.1 实现 strStr() — KMP 版

LeetCode 28。返回 pattern 在 text 中首次出现的位置，不存在返回 -1。

```cpp
#include <iostream>
#include <string>
#include <vector>

class Solution {
public:
    int strStr(std::string haystack, std::string needle) {
        if (needle.empty()) return 0;
        int n = haystack.size(), m = needle.size();
        std::vector<int> next = buildNext(needle);
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j > 0 && haystack[i] != needle[j]) j = next[j - 1];
            if (haystack[i] == needle[j]) ++j;
            if (j == m) return i - m + 1;
        }
        return -1;
    }

private:
    std::vector<int> buildNext(const std::string& p) {
        int m = p.size();
        std::vector<int> next(m, 0);
        int j = 0;
        for (int i = 1; i < m; ++i) {
            while (j > 0 && p[i] != p[j]) j = next[j - 1];
            if (p[i] == p[j]) ++j;
            next[i] = j;
        }
        return next;
    }
};

int main() {
    Solution sol;
    std::cout << sol.strStr("sadbutsad", "sad") << "\n";    // 0
    std::cout << sol.strStr("leetcode", "leeto") << "\n";   // -1
    return 0;
}

7.2 重复叠加字符串匹配

LeetCode 686。给定 a 和 b，求 a 重复叠加多少次后 b 成为其子串。

思路：最多叠加到 ceil(len(b)/len(a)) + 1 次，再用 KMP 匹配。

#include <iostream>
#include <string>
#include <vector>

class Solution {
public:
    int repeatedStringMatch(std::string a, std::string b) {
        int n = a.size(), m = b.size();
        int repeat = (m + n - 1) / n + 1;
        std::string s;
        for (int i = 0; i < repeat; ++i) s += a;
        std::vector<int> next = buildNext(b);
        int j = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            while (j > 0 && s[i] != b[j]) j = next[j - 1];
            if (s[i] == b[j]) ++j;
            if (j == m) {
                int end = i + 1;
                int ans = (end + n - 1) / n;
                if (ans > repeat) return -1;
                return ans;
            }
        }
        return -1;
    }

private:
    std::vector<int> buildNext(const std::string& p) {
        int m = p.size();
        std::vector<int> next(m, 0);
        for (int i = 1, j = 0; i < m; ++i) {
            while (j > 0 && p[i] != p[j]) j = next[j - 1];
            if (p[i] == p[j]) ++j;
            next[i] = j;
        }
        return next;
    }
};

int main() {
    Solution sol;
    std::cout << sol.repeatedStringMatch("abcd", "cdabcdab") << "\n";  // 3
    std::cout << sol.repeatedStringMatch("a", "aa") << "\n";           // 2
    return 0;
}

7.3 最短回文串

LeetCode 214。在字符串前面添加最少字符使其变成回文串。

核心：将 s 反转后拼接 s + '#' + rev(s)，用 KMP 求最长公共前后缀，前缀部分就是需要保留的最长回文前缀。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::string shortestPalindrome(std::string s) {
        std::string rev = s;
        std::reverse(rev.begin(), rev.end());
        std::string t = s + '#' + rev;
        std::vector<int> next = buildNext(t);
        int len = next.back();
        return rev.substr(0, s.size() - len) + s;
    }

private:
    std::vector<int> buildNext(const std::string& p) {
        int m = p.size();
        std::vector<int> next(m, 0);
        for (int i = 1, j = 0; i < m; ++i) {
            while (j > 0 && p[i] != p[j]) j = next[j - 1];
            if (p[i] == p[j]) ++j;
            next[i] = j;
        }
        return next;
    }
};

int main() {
    Solution sol;
    std::cout << sol.shortestPalindrome("aacecaaa") << "\n"; // aaacecaaa
    std::cout << sol.shortestPalindrome("abcd") << "\n";     // dcbabcd
    return 0;
}

7.4 旋转字符串匹配

判断字符串 b 是否能由 a 旋转得到（如 "abcde" 旋转得 "cdeab"）。

等价于判断 b 是否是 a + a 的子串。用 KMP 一次匹配。

#include <iostream>
#include <string>
#include <vector>

class Solution {
public:
    bool rotateString(std::string a, std::string b) {
        if (a.size() != b.size()) return false;
        if (a == b) return true;
        std::string doubled = a + a;
        return kmpSearch(doubled, b) != -1;
    }

private:
    int kmpSearch(const std::string& text, const std::string& pattern) {
        int n = text.size(), m = pattern.size();
        if (m == 0) return 0;
        std::vector<int> next(m, 0);
        for (int i = 1, j = 0; i < m; ++i) {
            while (j > 0 && pattern[i] != pattern[j]) j = next[j - 1];
            if (pattern[i] == pattern[j]) ++j;
            next[i] = j;
        }
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j > 0 && text[i] != pattern[j]) j = next[j - 1];
            if (text[i] == pattern[j]) ++j;
            if (j == m) return i - m + 1;
        }
        return -1;
    }
};

int main() {
    Solution sol;
    std::cout << std::boolalpha;
    std::cout << sol.rotateString("abcde", "cdeab") << "\n";  // true
    std::cout << sol.rotateString("abcde", "abced") << "\n";  // false
    return 0;
}