二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
一、代码查看
#include <iostream> #include <string> #include <vector> using namespace std; int f(const string &s, const string &t) { int n = s.length(), m = t.length(); vector<int> shift(128, m + 1); int i, j; for (j = 0; j < m; j++) shift[t[j]] = m - j; for (i = 0; i <= n - m; i += shift[s[i + m]]) { j = 0; while (j < m && s[i +j] == t[j]) j++; if (j == m) return i; } return -1;}int main(){ string a, b; cin >> a >> b; cout << f(a, b) << endl; return 0;}二、代码分析
从第18 ~ 22 行代码可以很明显得看出，该题的目的是从s字符串中找出第一个字串t的位置。
for (i = 0; i <= n - m; i += shift[s[i + m]]) { j = 0; while (j < m && s[i +j] == t[j]) j++; if (j == m) return i;}j 是 t 串的下标，每次从 0 开始，和 s 串配对，发现不对结束内循环。最后判断 j 是否停留在 t 串的最后一个下标，如果是就说明找到了，便把 i 返回去。
理解了代码的大致意义后，我们从头开始看。
string a, b;cin >> a >> b;cout << f(a, b) << endl;以上是 main() 函数中所做的，意义很简单，就是输入两个字符串 s, t，然后调用 f(s, t) 函数去找字串并输出结果。
接着我们看看 f(s, t) 函数中的内容。
int n = s.length(), m = t.length(); 这句话将 s 串和 t 串的长度记录在两个变量里。
vector<int> shift(128, m + 1); for (j = 0; j < m; j++) shift[t[j]] = m - j;接下来是重点。shift容器中存的是跳过的步数。
第一次先访问s[0], 从0开始与 t 比较，如果对上了就返回，否则 i 要后移，但是后移几位就要看情况了。为了节省时间，我们要看看 s[i + m]。比如 t = “day”，这个时候我们看看s[i + m]是不是d、a、y中的一个，如果是d，那就从[3]开始，如果是a，那就从[2]开始，如果是y，就从下一个，也就是[1]开始，如果都不是，那就说明近3个不会出答案，那么就+4跳过。
这步看不懂评论区见
三、题目分析
判断题
1.（1 分）当输入为“abcde fg”时，输出为-1。（对）【因为abcde中找不到fg】
2. 当输入为“abbababbbab abab”时，输出为 4。（错）【因为字串abab起始位置从0开始，是3】
3. 当输入为“GoodLuckCsp2022 22”时，第 20 行的“j++”语句执行次数为 2。（错）【第一次++是第一个2后，第二次在第二个2后】
单选题
该算法最坏情况下的时间复杂度为（D）。
A. O(n + m)
B. O(n log m)
C. O(m log n)
D. O(nm)
【外循环n内循环m，所以n * m】
f(a, b) 与下列（A）语句的功能最类似。
A. a.find(b)
B. a.rfind(b)C. a.substr(b)
D. a.compare(b)
【.find()函数用于找字串，必须知道，写代码】
当输入为“baaabaaabaaabaaaa aaaa”，第 20 行的“j++”语句执行次数为 （B）。
A. 9
B. 10C. 11
D. 12
【第一次s[0] = 'b'，直接跳过，s[i + 5] = 'a'，s[5]~s[7]执行了3次，s[5 + 4] = 'a'，执行3次，s[9 + 4] = 'a'，执行4次，共10次。
baaabaaabaaabaaaa 标记+过的下标都执行了一次j++
+++ +++ ++++
】
看不懂评论区见，大家一起解答，有问题请反应~