题意

给一主串s,有m次询问,每次询问串t是否为s的子序列


题解

很简单的一道题呀!
考虑最暴力的方法:每次询问的串直接在主串上扫描复杂度为O(nsumbi)
但其实这其中有很多步骤是没有意义的
我们只需要把每种字母出现的位置存进一个vector里,然后对于每次询问,只需循环模拟二分就可以啦!
时间复杂度为O(len
log(n))

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
//const int mod = 998244353;
//LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
int n,pos[maxn],m;
char s[maxn],t[maxn];
VI G[27];
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        G[s[i]-'a'].pb(i);
    }
    for(int i=0;i<26;i++) G[i].pb(n+1);
    int q;scanf("%d",&q);
    while(q--){
        scanf("%s",s+1);
        m=strlen(s+1);
        int np=0;
        for(int i=1;i<=m;i++){
            np=upper_bound(G[s[i]-'a'].begin(),G[s[i]-'a'].end(),np)-G[s[i]-'a'].begin();
            np=G[s[i]-'a'][np];
            //cout<<np<<endl;
            if(np>n){
                break;
            }
        }
        if(np>n) printf("No\n");
        else printf("Yes\n");
    }
}