一、构建

建立序列自动机
ne[i][j]数组存的是在 s 中第 i 位后面第一个 j 字母出现的位置。

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

二、不同子序列个数

方法一：借助序列自动机

给出一个字符串统计其本质不同的子序列个数，记忆化搜索。
$f_i$记录$i\to n$不同子序列的个数
目前在$u$位置有两种选择：①继续在后面添加字符构成更长的子序列②$u$为子序列末尾
注意：空序列也算一个子序列

int dfs(int u)
{
    if(f[u]) return f[u];
    for(int i=0; i<26; i++)
        if(ne[u][i]) f[u] += dfs(ne[u][i]);
    return ++f[u];
}
// 询问dfs(0)即可得出答案

方法二：动态规划

状态表示：$f_(i)$表示考虑前$i$个字符不重复子序列的个数
状态转移：对于第$i$个字符，有两种选择，如果不选择方案数是$f_{i-1}$，如果选择方案数是$f_{i-1}-f_{k-1}$，$k$是在$i$之前最后一次$s_i$出现的位置。

模板题——子序列匹配

Subsequence
月月查华华的手机

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
const int N=100010;
int ne[N][30];
char s[N],t[1010];
int n,q;
void build()
{
    for(int i=n;i;i--)
    {
        for(int j=0;j<26;j++)
            ne[i-1][j]=ne[i][j];
        ne[i-1][s[i]-'a']=i;
    }
}
int main()
{   
    scanf("%s",s+1);
    n=strlen(s+1);
    build();
    scanf("%d",&q);
    while(q--)
    {
        scanf("%s",t);
        bool ok=1;
        int len=strlen(t);
        for(int i=0,now=0;i<len;i++)
        {
            now=ne[now][t[i]-'a'];
            if(!now) 
            {
                ok=0;
                break;
            }
        }
        if(ok) printf("YES\n");
        else printf("NO\n");
    }
    return 0;

}

参考大佬博客