题目链接：月月查华华的手机（NC23053）

题意

给定华华的昵称字符串 A，再给出 N 个昵称 Bi。

如果 Bi 是 A 的子序列，就输出 Yes，否则输出 No。

所谓子序列，是指从原字符串中删除若干字符（也可以一个都不删），并且不改变剩余字符的相对顺序，得到的新字符串。

例如，ace 是 abcde 的子序列，而 aec 不是。

数据范围

• 1 ≤ |A| ≤ 10^6
• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ Σ|Bi| ≤ 10^6

如果对每个 Bi 都从头扫描一次 A，最坏复杂度会达到 O(N|A|)，显然无法通过。因此，需要先预处理 A，让每次匹配都能快速跳到下一个需要的字符。

思路：预处理下一个字符的位置

定义：

nxt[i][c]

表示在 A 的位置 i 之后，字符 c 第一次出现的位置。如果后面没有字符 c，则值为 -1。

再用数组 first[c] 记录字符 c 在整个字符串中第一次出现的位置。

如何预处理

从右向左扫描 A，使用 last[c] 保存当前位置右边最近的字符 c 的下标。

对于每个位置 i：

1. 将当前的 last 复制到 nxt[i]；
2. 再令 last[A[i]] = i。

必须先复制、后更新，因为 nxt[i][c] 表示的是位置 i 之后 的字符，不能包含 i 本身。

扫描结束后，last[c] 就是字符 c 在 A 中第一次出现的位置，可以直接作为 first[c] 使用。

如何回答询问

对于一个昵称 Bi：

1. 用 first[Bi[0]] 找到第一个字符的位置；
2. 假设当前匹配位置为 pos，则通过 nxt[pos][Bi[i]] 找到下一个字符；
3. 如果某一步得到 -1，说明无法继续匹配，输出 No；
4. 如果所有字符都成功匹配，输出 Yes。

正确性说明

每次通过 nxt[pos][c] 选择的，都是 pos 之后最早出现的字符 c。

选择最早位置不会让后续匹配变差，因为它会为剩余字符保留尽可能长的后缀。如果连最早出现的合法位置都无法完成后续匹配，那么选择更靠后的位置也不可能成功。

因此，所有字符都能依次找到时，Bi 是 A 的子序列；任何一步找不到时，Bi 都不是 A 的子序列。

复杂度分析

• 预处理时间复杂度：O(26|A|)
• 所有询问时间复杂度：O(Σ|Bi|)
• 空间复杂度：O(26|A|)

当 |A| = 10^6 时，nxt 大约占用 100 MiB，低于题目的 256 MiB 空间限制。

C++ 代码

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

const int MAX_LEN = 1000000 + 5;

int nxt[MAX_LEN][26];
int firstPos[26];

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

    string a;
    cin >> a;

    int len = static_cast<int>(a.size());
    memset(firstPos, -1, sizeof(firstPos));

    // firstPos 在扫描过程中充当 last 数组。
    // nxt[i][c] 表示位置 i 之后，字符 c 第一次出现的位置。
    for (int i = len - 1; i >= 0; --i) {
        for (int c = 0; c < 26; ++c) {
            nxt[i][c] = firstPos[c];
        }
        firstPos[a[i] - 'a'] = i;
    }

    int n;
    cin >> n;

    while (n--) {
        string girl;
        cin >> girl;

        int pos = firstPos[girl[0] - 'a'];
        bool ok = (pos != -1);

        for (int i = 1; ok && i < static_cast<int>(girl.size()); ++i) {
            pos = nxt[pos][girl[i] - 'a'];
            if (pos == -1) {
                ok = false;
            }
        }

        cout << (ok ? "Yes\n" : "No\n");
    }

    return 0;
}

易错点

1. memset 的第三个参数是字节数

普通数组没有成员函数 .size()，应写成：

memset(firstPos, -1, sizeof(firstPos));

memset 的参数顺序是：数组地址、填充值、字节数。

2. 不要为每个询问重新扫描 A

下面的写法在询问很多时会超时：

for (int i = 0; i < len; ++i) {
    if (girl[0] == a[i]) {
        pos = i;
        break;
    }
}

预处理完成后，直接使用：

int pos = firstPos[girl[0] - 'a'];

即可在 O(1) 时间内找到第一个字符。

3. 更新的是原字符串中的位置

匹配下一个字符后应该写：

pos = nxt[pos][girl[i] - 'a'];

不能写成 pos = i，因为 i 是 girl 中的下标，而 pos 必须表示字符在原字符串 A 中的位置。

4. 循环变量不能重复增加

for 循环末尾已经会执行 ++i，循环体中不要再次执行 i++，否则会跳过字符，最后还可能访问越界。

5. 注意输出效率

题目明确提醒注意输出效率。关闭 C++ 流同步并使用 \n，避免频繁使用会强制刷新缓冲区的 endl：

ios::sync_with_stdio(false);
cin.tie(nullptr);