solution

本来看成了是子段,以为要用ac自动机。
注意到就是要求一个字符串是不是母串的子序列(也就是不要求连续)。这是一个非常经典的问题,我们用表示母串中i这个位置的下一个字符j出现的位置。

如何求这个数组呢?如果,那么。否则。这样就可以很快的求出f数组。

判断一个字符串是不是母串的子序列的时候,直接从0号位置开始,每次跳到原序列中下次出现t[i]的位置即可,如果跳出了母串的最后一个字符,表示不是母串的子序列。

code

/*
* @Author: wxyww
* @Date: 2020-04-03 06:32:01
* @Last Modified time: 2020-04-03 06:36:08
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int f[N][26],n;
char s[N];
void solve() {
    int p = 0;
    for(int i = 1;s[i];++i) {
        p = f[p][s[i] - 'a'];
        if(p > n) {
            puts("No");return;
        }
    }
    puts("Yes");
}
int main() {
    scanf("%s",s + 1);
    n = strlen(s + 1);

    for(int i = 0;i < 26;++i) f[n][i] = n + 1;

    for(int i = n - 1;i >= 0;--i) {
        for(int j = 0;j < 26;++j)
            f[i][j] = f[i + 1][j];
        f[i][s[i + 1] - 'a'] = i + 1;
    }

    int m = read();
    while(m--) {
        scanf("%s",s + 1);
        solve();
    }

    return 0;
}