题解 | #月月查华华的手机#

这是一个经典的子序列匹配问题。我们需要在大量的查询中，快速判断字符串 是否是字符串 的子序列。

核心思想：贪心策略 + 预处理（序列自动机/跳转表）

• 贪心策略： 判断 是否为 的子序列，最直观的方法是贪心。我们需要在 中按顺序找到 的每一个字符。当我们找到了 的第 个字符在 中的位置 后，寻找 的第 个字符时，必须在 的 位置之后寻找。为了尽可能让后面的字符匹配成功，我们应该总是选择 中最早出现的那个字符。

• 朴素做法的瓶颈： 如果对于每一个查询 ，我们都在 中线性扫描寻找字符，最坏情况下的时间复杂度是 。考虑到 和 都可达 ，这个复杂度高达 ，肯定会超时。

• 优化方案： 我们需要快速回答这样一个问题：“在字符串 的第 个位置之后，字符 'x' 第一次出现的位置在哪里？” 如果我们能以 的时间回答这个问题，那么判断一个长度为 的字符串 是否为子序列的时间复杂度就能降为 。 这可以通过预处理来实现。我们可以构建一个二维数组（通常称为“序列自动机”或“Next数组”），记录每个位置之后各个字符首次出现的索引。

算法步骤

第一步：预处理（构建跳转表）

我们需要构建一个二维数组 nxt[len(A) + 1][26]。 nxt[i][j] 表示：在字符串 的第 个位置（包含或不包含取决于具体实现，通常指 之后）开始，字符 （对应 'a'-'z'）第一次出现的位置下标。

1. 初始化一个大小为 26 的数组 pos，用于记录当前字符最后一次出现的下标，初始值为无效值（如 -1 或无穷大）。
2. 从后往前遍历字符串 （从 到 ）：
   • 对于当前位置 和字符 ：
     • 更新 pos[A[i]] 为当前下标 。
   • 对于每一个字母 'a' 到 'z'（索引 从 0 到 25）：
     • 将 nxt[i][k] 设为 pos[k]。即记录在当前位置 往后看，字符 最近的一次出现位置。
   • 注：为了处理方便，通常将 nxt[i][c] 定义为在位置 之后（不含 ）字符 的位置。具体实现时可根据习惯调整，例如从后往前填表时，nxt[i][c] 继承 nxt[i+1][c]，并更新当前字符的跳转位置。

第二步：处理查询

对于输入的每一个 ：

1. 设置一个变量 current_index 指向 的起始位置之前（例如 -1 或 0，取决于预处理的索引方式）。
2. 遍历 中的每一个字符 char：
   • 查表：查看 nxt[current_index][char] 是否存在有效值。
   • 如果存在：说明在 中当前位置之后找到了该字符。更新 current_index 为查到的新位置。
   • 如果不存在：说明 中剩余部分没有该字符了， 不是子序列。终止循环，输出 "No"。
3. 如果 的所有字符都成功找到，输出 "Yes"。

复杂度分析

假设 为字符串 A 的长度， 为所有查询字符串长度之和， 为字符集大小（本题为 26）。

时间复杂度

1. 预处理阶段： 我们需要从后往前遍历 ，对每个位置填充 26 个字符的跳转信息。 复杂度为：。

2. 查询阶段： 对于每个 ，我们只需要遍历它的每一个字符，每次跳转是 的。 总复杂度为：。

3. 总时间复杂度： 。

空间复杂度

我们需要一个二维数组 nxt 来存储跳转表。 大小为：。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string A;
    cin >> A;

    int n = A.size();
    vector<vector<int>> next(n + 1, vector<int>(26, -1));
    for (int i = n - 1; i >= 0; i--) {
        int c = A[i] - 'a';
        for (int j = 0; j < 26; j++)
            next[i][j] = next[i + 1][j];
        next[i][c] = i;
    }

    int N;
    cin >> N;
    while (N--) {
        string B;
        cin >> B;

        int cur = 0;
        bool ok = true;
        for (char ch : B) {
            int c = ch - 'a';
            cur = next[cur][c];
            if (cur == -1) {
                ok = false;
                break;
            } else {
                cur++;
            }
        }

        if (ok) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}