组合题
#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题 判断题

(1 分)当输入为“abcde fg”时,输出为-1。( )

A 正确
B 错误
第2题 判断题

当输入为“abbababbbab abab”时,输出为 4。( )

A 正确
B 错误
第3题 判断题

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

A 正确
B 错误
第4题 单选题

该算法最坏情况下的时间复杂度为( )。

A

 O(n + m)

B

O(n log m)

C

O(m log n)

D

 O(nm)

第5题 单选题

f(a, b)与下列( )语句的功能最类似。

A

a.find(b)

B

a.rfind(b)

C

a.substr(b)

D

a.compare(b)

第6题 单选题

当输入为“baaabaaabaaabaaaa aaaa”,第 20 行的“j++”语句执行次数为( )。

A

9

B

10

C

11

D

12

赣ICP备20007335号-2