题意
给一主串s,有m次询问,每次询问串t是否为s的子序列
题解
很简单的一道题呀!
考虑最暴力的方法:每次询问的串直接在主串上扫描复杂度为O(nsumbi)
但其实这其中有很多步骤是没有意义的
我们只需要把每种字母出现的位置存进一个vector里,然后对于每次询问,只需循环模拟二分就可以啦!
时间复杂度为O(lenlog(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"); } }