第 22 篇 的图算法处理「关系」；本篇进入算法面试的两大支柱：字符串搜索（在文本中找模式）和动态规划（把大问题拆成重叠子问题）。KMP 和 Boyer-Moore 解决搜索，背包和 LCS 解决 DP——掌握这些，LeetCode 中等题大半有思路。

demo：ref/cpp_demo/algorithms/string_search/ + ref/cpp_demo/algorithms/dynamic_programming/。

这是「现代 C++ 实战」系列的第 23 篇。建议先读 第 22 篇：图算法。

一、字符串搜索全景

在文本 text（长度 n）中查找模式 pattern（长度 m）：

算法 时间 思路 适用
暴力 O(nm) 每个位置逐字符比 短模式、教学
KMP O(n+m) 前缀函数，失配不回退 text 通用、面试必考
Boyer-Moore 最好 O(n/m) 从右向左，坏字符跳跃 长模式、实际文本搜索
Rabin-Karp 平均 O(n+m) 滚动哈希，先比哈希再验证 多模式匹配 
1
2
3
4
text:    A B A B D A B A C D A B A B C A B A B
pattern: A B A B
匹配:    ↑       ↑               ↑
位置:    0       10              15

二、暴力匹配：基线

1
2
3
4
5
6
7
8
9
10
11
std::vector<int> bruteForceSearch(const std::string& text,
                                  const std::string& pattern) {
    int n = text.length(), m = pattern.length();
    std::vector<int> positions;
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) j++;
        if (j == m) positions.push_back(i);
    }
    return positions;
}

最坏情况：text = "AAAA...AA", pattern = "AAA...AB" → 每次比较几乎走满 m，总 O(nm)。

三、KMP：前缀函数，不回退 text

核心思想：模式串失配时，利用已匹配部分的最长相等前后缀（LPS），跳过已知不可能的位置。

1
2
3
4
pattern: A B A B
LPS:     0 0 1 2
         ↑     ↑
      无前后缀  "AB" = "AB"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::vector<int> computeLPS(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> lps(m, 0);
    int len = 0, i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];  // 回退，不移动 i
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

匹配时 text 的指针 i 只前进不后退：

1
2
3
4
5
// 失配时：j = lps[j-1]，而非 i 回退
if (pattern[j] != text[i]) {
  if (j != 0) j = lps[j - 1];
  else i++;
}
复杂度 值
预处理 LPS O(m)
搜索 O(n)
总计 O(n+m)

应用：编译器词法分析、DNA 序列匹配、Git diff 中的子串查找。

四、Boyer-Moore：从右向左跳

从模式串末尾开始比较，失配时根据坏字符规则大幅跳跃：

1
2
3
4
text:    ... H O R S E ...
pattern:     S N A P
比较:          ↑ 从右向左
坏字符 H 不在 pattern 中 → 整个模式右移 m 位
1
2
3
4
5
6
7
8
// 坏字符表：字符 c 在 pattern 中最后出现位置距末尾的距离
std::unordered_map<char, int> badCharHeuristic(const std::string& pattern) {
    int m = pattern.length();
    std::unordered_map<char, int> badChar;
    for (int i = 0; i < m - 1; i++)
        badChar[pattern[i]] = m - i - 1;
    return badChar;
}

实际工程（grep、文本编辑器）常用 BM 或其变种；完整版还有好后缀规则，demo 实现了坏字符启发式。

五、Rabin-Karp：滚动哈希

把长度为 m 的窗口映射为哈希值，先比哈希再逐字符验证：

1
2
// 滚动：去掉 text[i]，加入 text[i+m]
textHash = (256 * (textHash - text[i] * h) + text[i + m]) % PRIME;
优点 缺点
多模式并行（同一 text 滚一次） 哈希冲突需二次验证
实现简洁 需选大质数减少碰撞

应用：抄袭检测、多关键词过滤、生物信息学批量匹配。

六、动态规划入门

三要素：

  1. 状态：dp[i] 或 dp[i][j] 表示什么
  2. 转移：当前状态如何从之前状态推导
  3. 边界：初始值

两种实现：

方式 方向 实现
记忆化（Memoization） 自顶向下 递归 + unordered_map 缓存
递推（Tabulation） 自底向上 循环填表

斐波那契对比（demo 测 n=40）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 朴素递归 O(2^n) — 重复计算爆炸
long long fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

// 递推 O(n)，空间 O(1)
long long fib_iterative(int n) {
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long cur = prev1 + prev2;
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

七、经典 DP 问题

0-1 背包

n 个物品，重量 w[i]、价值 v[i]，背包容量 W，每件最多选一次：

1
2
dp[i][j] = max(不选第i个, 选第i个)
         = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

一维优化：容量 j 从大到小遍历，避免同一轮重复使用物品：

1
2
3
for (int i = 0; i < n; i++)
    for (int j = capacity; j >= weights[i]; j--)
        dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);

demo 结果：重量 {2,3,4,5}、价值 {3,4,5,6}、容量 8 → 最大价值 10。

最长公共子序列（LCS）

1
2
3
4
if (s1[i-1] == s2[j-1])
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);

"ABCDGH" vs "AEDFHR" → LCS 长度 3，字符串 "ADH"。

最长递增子序列（LIS）

方法 时间 思路
DP O(n²) dp[i] = 以 nums[i] 结尾的 LIS 长度
贪心+二分 O(n log n) 维护 tail 数组，lower_bound 替换

{10,9,2,5,3,7,101,18} → LIS 长度 4（如 2,3,7,101）。

编辑距离

s1 变 s2 的最少操作（插入/删除/替换，各代价 1）：

1
2
3
4
dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1]
         : 1 + min(dp[i-1][j],    // 删
                   dp[i][j-1],    // 插
                   dp[i-1][j-1]); // 换

"kitten" → "sitting"：距离 3（k→s, e→i, 插入 g）。

应用：拼写纠错、DNA 比对、diff 算法基础。

硬币找零

凑金额 amount 的最少硬币数（硬币无限）：

1
2
3
4
5
dp[0] = 0;
for (int i = 1; i <= amount; i++)
    for (int coin : coins)
        if (i >= coin && dp[i-coin] != INT_MAX)
            dp[i] = std::min(dp[i], dp[i-coin] + 1);

硬币 {1,3,4}、金额 6 → 2 枚（3+3）。

八、选型速查

问题类型 首选算法
单模式精确匹配 KMP
长文本搜索 Boyer-Moore
多模式 / 哈希场景 Rabin-Karp
最优化（选/不选） 0-1 背包 DP
两串相似度 LCS / 编辑距离
子序列最值 LIS
最少步数凑目标 硬币找零 BFS 或 DP

九、运行 demo

1
2
3
4
5
6
7
8
9
10
# 字符串搜索
cd ref/cpp_demo/algorithms/string_search
g++ -std=c++17 -o brute_force brute_force.cpp && ./brute_force
g++ -std=c++17 -o kmp kmp.cpp && ./kmp
g++ -std=c++17 -o boyer_moore boyer_moore.cpp && ./boyer_moore
g++ -std=c++17 -o rabin_karp rabin_karp.cpp && ./rabin_karp

# 动态规划
cd ../dynamic_programming
g++ -std=c++17 -O2 -o dp_demo dp_demo.cpp && ./dp_demo
demo 预期输出要点
四个搜索 ABAB 在位置 0 10 15
dp_demo 斐波那契性能对比、背包 10、LCS “ADH”、LIS 4、编辑距离 3、硬币 2

十、小结

模块 要点
暴力 O(nm) 基线
KMP LPS 数组，text 不回退
Boyer-Moore 右向左 + 坏字符跳跃
Rabin-Karp 滚动哈希 + 验证
DP 状态 + 转移 + 边界；记忆化 vs 递推
经典题 背包、LCS、LIS、编辑距离、硬币找零

第三季算法篇收官。下一篇进入第四季进阶项目：用 cpp-httplib 搭 REST 服务、nlohmann/json 做序列化——见 第 24 篇：HTTP 服务与 JSON（计划）。