CSP-S 2022 第一轮 第18题：当输入为“GoodLuckCsp2022 22”时，第20行的“j++”语句执行

题目

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

当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 2。

选项

• T. 正确
• F. 错误

答案

T

题解

答案：T. 正确。

s = "GoodLuckCsp2022"，t = "22"，所以 m = 2。

第 15～16 行设置跳转距离：shift['2'] 先被赋值为 2，随后被覆盖为 1；其他字符的跳转距离均为 3。

第 18 行每次根据 s[i + 2] 决定下一次的 i：

当 i = 13 时，s[13] 和 s[14] 都是 '2'，j 从 0 增加到 2，随后函数返回。

因此，第 20 行的 j++ 总共执行 2 次。