【每日一题】4月2日

序列自动机模板题。
建出后直接看能不能被自动机接受就可以了。

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e6 + 5;
char str[MAXN];
int n;

struct SEQAM{ // 序列自动机 使用了类似 trie 图优化的东西
    int ch[MAXN][26],frm[MAXN],tot = 0,rt = 0;

    inline void build(){
        CLR(ch,0);CLR(frm,0x3f);
        FOR(i,1,n) frm[str[i]-'a'] = std::min(frm[str[i]-'a'],i);
        ROF(i,n,0){
            if(i < n){
                ch[i][str[i+1]-'a'] = i+1;
            }
            FOR(j,0,25){
                if(!ch[i+1][j]&&!ch[i][j]) ch[i][j] = frm[j];
                else if(!ch[i][j]) ch[i][j] = ch[i+1][j];
            }
        }
    }
}T;
char q[MAXN];
int main(){
    scanf("%s",str+1);n = strlen(str+1);
    T.build();
    int t;scanf("%d",&t);
    FOR(i,1,t){
        scanf("%s",q+1);int tt = strlen(q+1);
        int v = 0;
        FOR(j,1,tt){
            if(T.ch[v][q[j]-'a'] == 0x3f3f3f3f || T.ch[v][q[j]-'a'] <= v){
                v = 0x3f3f3f3f;
                break;
            }
            v = T.ch[v][q[j]-'a'];
        }
        puts(v!=0x3f3f3f3f?"Yes":"No");
    }
    return 0;
}