CSP-S 提高级 · CSP 2022 提高级第一轮 第 16 题

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

（1）

1  #include <iostream> 
2  #include <string> 
3  #include <vector> 
4  
5  using namespace std; 
6  
7  int f(const string &s, const string &t) 
8  { 
9      int n = s.length(), m = t.length(); 
10 
11     vector<int> shift(128, m + 1); 
12 
13     int i, j;
14 
15     for (j = 0; j < m; j++)
16         shift[t[j]] = m - j;
17 
18     for (i =0; i<= n - m; i += shift[s[i + m]]){
19         j =0;
20         while(j < m && s[i +j] == t[j]) j++;
21         if (j == m) return i;
22     }
23 
24     return -1;
25 }
26 
27 int main()
28 {
29     string a ,b;
30     cin >> a >> b;
31     cout << f(a, b) << endl;
32     return 0;
33 }

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：

判断题

1. （1 分）当输入为“abcde fg”时，输出为-1。 2. 当输入为“abbababbbab abab”时，输出为 4。 3. 当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 2。

**单选

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

程序功能： BM 算法简化版（仅坏字符规则）。函数 f(s,t) 返回 t 在 s 中首次出现的下标，找不到返回 -1。

• 预处理：shift[c] = m - j（字符 c 在 t 中最后出现位置到末尾的距离）
• 匹配：从右向左比较，不匹配时 i += shift[s[i+m]] 跳跃

各题要点： 1. 正确 ✅ — "abcde" 找不到 "fg"，返回 -1 2. 错误 ❌ — 算法实际返回 -1，不是 4 3. 正确 ✅ — "22" 匹配两次，j++ 执行 2 次 4. 最坏 O(nm) — 选 D，如 s="aaaaaa", t="baa" 5. 相当于 a.find(b) — 选 A（首次出现位置） 6. j++ 执行 10 次 — 选 B

判断题 2 容易翻车： 人眼直接看确实"abbababbbab"里好像有"abab"，但需要实际模拟才能判断。

单选题 5 容易误选 rfind： rfind 是从右向左找最后一次出现，而本函数找的是第一次出现（从 i=0 开始递增），所以是 find。

单选题 6 需要精确计数： j++ 在 while 循环中每匹配一个字符加一次，要逐次追踪才能得到正确数字。

考察知识点： 字符串算法 — Boyer-Moore 坏字符规则

坏字符规则（Bad Character Rule）的工作原理：

1. 预处理： 遍历模式串 t，对每个字符 c，shift[c] = m - 1 - lastPos[c]，即该字符在 t 中最后出现位置距末尾的距离

2. 匹配过程： - 将 t 与 s[i..i+m-1] 对齐 - 从右向左比较（j = m-1 → 0） - 遇到不匹配：看 s[i+j] 这个字符的 shift 值，i += shift[s[i+j]] - 如果 shift[s[i+j]] ≤ 0，则 i++

实际上本题的代码中 shift 是正数且至少为 1（因为公式是 m - j，j 最大为 m-1，所以 shift 最小为 1）。

3. 为什么能跳着走？ 如果当前窗口的末尾字符 s[i+m] 在 t 中出现了，我们可以把 t 向右移，使这个字符对齐到 t 中最后一次出现的位置。这样跳过的距离就是 shift[s[i+m]]。

本题实现的简化： 标准 BM 算法的 shift 是 m - 1 - lastPos[c]，而这里用的是 m - j。实现差异不影响功能。

BM 算法的效率：

• 最好情况：O(n/m)（每次跳过 m 个字符）
• 最坏情况：O(nm)（如 s="aaaa...a", t="baa"）
• 实际应用：通常比 KMP 更快，常用于文本编辑器、grep 等工具

技巧： 阅读程序题中遇到字符串匹配算法，先找 shift 预处理部分理解跳跃规则，再代入小数据手动追踪 2-3 步。