Solution

直观的想法是直接扫描两个字符串进行比较。这样的复杂度是 的。

然后可以发现子序列中字母的相对位置是不变的，所以可以维护一个数组 ， 表示第 个位置之后最近的字母 所在的位置。这个数组可以 处理： ，然后在倒序循环一遍即可预处理出 数组。

对于每个要判断的字符串 ，建立一个指针 ，初始值为 。然后判断 的每一位是否在 中出现，并更新指针 即可。

时间复杂度： 。字符集常数较大。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e6+10;
int n,m,nxt[maxn][30];
char s[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>s+1;
    m=strlen(s+1);
    for(int i=1;i<=m;i++)
        nxt[i-1][s[i]-'a']=i;
    for(int i=m-1;i>=0;i--)
        for(int j=0;j<26;j++)
            if(!nxt[i][j])
                nxt[i][j]=nxt[i+1][j];
    string t;
    int x,y;
    cin>>n;
    while(n--){
        cin>>t;
        m=t.size();
        x=y=0;
        for(int i=0;i<m;i++){
            x=nxt[x][t[i]-'a'];
            if(!x){
                y=1;
                break;
            }
        }
        if(y)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}