CSP-S 2022 第一轮 第19题：该算法最坏情况下的时间复杂度为（）。

题目

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

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

选项

• A. $O(n+m)$
• B. $O(n log m)$
• C. $O(m log n)$
• D. $O(nm)$

答案

D

题解

选 D. \(O(nm)\)，其中 \(n\) 是主串 s 的长度，\(m\) 是模式串 t 的长度。

分三步看：

1. 初始化 shift 数组：长度固定为 128，耗时 \(O(1)\)。
2. 预处理（第 15～16 行）：循环 \(m\) 次，耗时 \(O(m)\)。
3. 匹配（第 18～22 行）：
4. 外层循环每次至少向后移动 1 位，最多尝试 \(O(n)\) 次。
5. 内层 while 每次最多比较 \(m\) 个字符，耗时 \(O(m)\)。
6. 因此匹配过程的最坏时间复杂度为 \(O(nm)\)。

为什么跳跃没有避免这个最坏情况？ 可以构造：

``text s = aaaaaaaaaaaaaaaaaaaa…… t = aaaab ``

每次都比较到 t 的最后一个字符才失败，需要比较 \(m\) 次。而 t 中最后一个 a 在倒数第二位，因此 shift['a'] = 2，每次只向后移动 2 位，仍需要 \(O(n)\) 次尝试。

所以总时间复杂度为： \[ O(m+nm)=\boxed{O(nm)} \]