CSP-S 2022 第一轮 第17题：当输入为“abbababbbababab”时，输出为 4。

题目

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

当输入为“abbababbbab abab”时，输出为 4。

选项

• T. 正确
• F. 错误

答案

F

题解

选 F（错误），实际输出为 3。

cin >> a >> b 按空格读取两个字符串：

``text a = "abbababbbab" b = "abab" ``

函数 f(a, b) 返回 b 在 a 中第一次出现的起始下标，下标从 0 开始。

``text 下标：0 1 2 3 4 5 6 7 8 9 10 a： a b b a b a b b b a b b： a b a b ``

"abab" 从第 4 个字符开始，对应下标 3，所以输出为 3，不是 4。