月月查华华的手机

题目大意：给一个文本串和一个n，接着n个模板串，问文本串中是否有子序列和模板串相等

传送门

难度

暴力枚举一定超时的，要想到和AC自动机一样预处理的方法来优化暴力枚举

思路

预处理得到一个数组，从A数组的首字符开始获取B的首字符第一次出现的位置（如果第一个都不可以那么后面的也都不可以），再从这个位置开始找B下一个字符第一次出现的位置，一直下去直到失配或者匹配成功就结束了。
在这里定义一个数组nt[i][k],k [0,26-1],表示a[i]之后第一次出现'a'+k的位置，还有数组last[i],表示'a'+1最后一次出现的位置，那么就要从后往前遍历A，同时维护a[i];

复杂度：

直接暴力的复杂度是 (|A| * | |),枚举优化后在主串的每一位要覆盖之后第一个'a'~'z'出现的位置|A|*26,然后匹配每一个模式串B，只要线性的遍历一遍B就可以了|B|,总的复杂度就是(|A| * 26 + | |)

代码：

并不需要另外初始化

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
char a[1000005],b[1000005];
int    nt[1000005][26],last[26];
void init() {
    int i=strlen(a)-1;
    for(;i>=0;--i) {
        for(int j=0;j<26;++j)    nt[i][j]=last[j];
        last[a[i]-'a']=i; 
    }
}
bool solve() {
    int i=last[b[0]-'a'];
    if(i==0&&a[0]!=b[0])    return false;
    for(int j=1;b[j];++j) {
        i=nt[i][b[j]-'a'];
        if(i==0)    return false;
    }
    return true;
}
int main() {
    js;    int n;
    cin>>a>>n;
    init();
    while(n--) {
        cin>>b;
        if(solve())    puts("Yes");
        else puts("No");
    }
}