#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; }
假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:
(1 分)当输入为“abcde fg”时,输出为-1。( )
当输入为“abbababbbab abab”时,输出为 4。( )
当输入为“GoodLuckCsp2022 22”时,第 20 行的“j++”语句执行次数为 2。( )
该算法最坏情况下的时间复杂度为( )。
O(n + m)
O(n log m)
O(m log n)
O(nm)
f(a, b)与下列( )语句的功能最类似。
a.find(b)
a.rfind(b)
a.substr(b)
a.compare(b)
当输入为“baaabaaabaaabaaaa aaaa”,第 20 行的“j++”语句执行次数为( )。
9
10
11
12