CSP-S 2022 第一轮 第21题：当输入为“baaabaaabaaabaaaa aaaa”，第 20 行

题目

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 可见字符组成，完成下面的判断题和单选题：

当输入为“baaabaaabaaabaaaa aaaa”，第 20 行的“j++”语句执行次数为 （ ）。

选项

• A. 9
• B. 10
• C. 11
• D. 12

答案

B

题解

答案选 B，10 次。

关键是：i 不一定每次加 1，而 j++ 只在字符匹配成功时执行。 字符串下标从 0 开始。

t = "aaaa"，所以 m = 4。第 15～16 行反复给 shift['a'] 赋值为 4、3、2、1，最终：

• shift['a'] = 1
• shift['b'] = 5（保留初始值 m + 1）

每轮匹配结束后，根据 s[i + 4] 决定 i 增加多少：

因此总执行次数为：

\[ 0+3+2+1+0+4=\boxed{10} \]