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

demo：ref/cpp_demo/algorithms/string_search/（brute_force、kmp、boyer_moore、rabin_karp）+ ref/cpp_demo/algorithms/dynamic_programming/（dp_demo）。

这是「现代 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
12
13
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;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) break;
        }
        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
16
17
18
19
std::vector<int> computeLPS(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else if (len != 0) {
            len = lps[len - 1];  // 回退，不移动 i
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

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

1
2
3
4
5
6
7
8
// 节选自 KMPSearch 的主循环
if (j == m) {
    positions.push_back(i - j);  // 记录匹配
    j = lps[j - 1];              // 继续找下一个（允许重叠）
} else if (i < n && pattern[j] != text[i]) {
    if (j != 0) j = lps[j - 1];  // 失配：j 回退，i 不动
    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
比较:                ↑ 从右向左（P 对 E）
坏字符 E 不在 pattern 中 → 整个模式右移 m 位
1
2
3
4
5
6
7
8
9
10
// 坏字符表：字符 c 在 pattern[0..m-2] 中最后出现位置距末尾的距离
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; i++)
        badChar[pattern[i]] = m;          // 默认移动 m
    for (int i = 0; i < m - 1; i++)
        badChar[pattern[i]] = m - i - 1;  // 只更新到倒数第二个字符
    return badChar;
}

boyerMooreSearch 失配时查表（表中没有的字符取 m），按 shift += std::max(1, bcShift - (m - 1 - j)) 移动窗口；匹配成功后只右移 1 位，保证能找到重叠匹配。

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

五、Rabin-Karp：滚动哈希

把长度为 m 的窗口映射为哈希值，先比哈希再逐字符验证。demo rabinKarpSearch 以 256 为基数、PRIME = 101 取模（教学用的小质数），h = 256^(m-1) % PRIME：

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

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

六、动态规划入门

三要素：

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

两种实现：

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

斐波那契对比（demo 测 n=40，分别计时朴素递归、记忆化 fibonacci_memoization、递推三种写法）：

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

// 递推 O(n)，空间 O(1)
long long fibonacci_iterative(int n) {
    if (n <= 1) return n;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    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])

demo 同时实现了二维 knapsack_2d 与一维 knapsack_1d。一维优化：容量 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 → 二维、一维 DP 的最大价值都是 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（lcs_length），回溯 dp 表得到字符串 "ADH"（lcs_string）。

最长递增子序列（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），demo 的 lis_n2 与 lis_nlogn 结果一致。

编辑距离

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

1
2
3
4
5
6
7
8
9
10
// 边界：dp[0][j] = j，dp[i][0] = i
if (s1[i-1] == s2[j-1]) {
    dp[i][j] = dp[i-1][j-1];
} else {
    dp[i][j] = std::min({
        dp[i-1][j] + 1,      // 删除
        dp[i][j-1] + 1,      // 插入
        dp[i-1][j-1] + 1     // 替换
    });
}

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

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

硬币找零

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

1
2
3
4
5
6
std::vector<int> dp(amount + 1, INT_MAX);
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）。凑不出时 coin_change 返回 -1。

八、选型速查

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

九、运行 demo

1
2
3
4
5
6
7
8
# 字符串搜索（C++11，每个 .cpp 一个同名可执行文件）
cd ref/cpp_demo/algorithms/string_search
./build.sh --run              # 依次运行 4 个程序
./build.sh --run kmp          # 只运行一个（brute_force / boyer_moore / rabin_karp 同理）

# 动态规划（C++17，单个 dp_demo）
cd ../dynamic_programming
./build.sh --run
demo 预期输出要点
四个搜索 在 ABABDABACDABABCABAB 中找 ABAB，位置 0 10 15
dp_demo F(40) = 102334155 及三种写法耗时（朴素递归百毫秒级，另两种约 0 ms）、背包 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。