1 #include <iostream>2 #include <string>3 #include <vector>45 using namespace std;67 int f(const string &s, const string &t)8 {9 int n = s.length(), m = t.length();1011 vector<int> shift(128, m + 1);1213 int i, j;1415 for (j = 0; j < m; j++)16 shift[t[j]] = m - j;1718 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 }2324 return -1;25 }2627 int main()28 {29 string a ,b;30 cin >> a >> b;31 cout << f(a, b) << endl;32 return 0;33 }假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:
判断题
(1 分)当输入为“abcde fg”时,输出为-1。
当输入为“abbababbbab abab”时,输出为 4。
当输入为“GoodLuckCsp2022 22”时,第 20 行的“j++”语句执行次数为 2。 单选题
该算法最坏情况下的时间复杂度为( )。
f(a, b) 与下列( )语句的功能最类似。
当输入为“baaabaaabaaabaaaa aaaa”,第 20 行的“j++”语句执行次数为 ( )。