【每日一题】月月查华华的手机

思路：
m次询问看字符串是不是给定字符串的子序列
暴力的做法就是直接两个循环去匹配 复杂度m * strlen(a) * Σ(strlen(b)) 这复杂度显然是不可接受的
那么考虑一下预处理
cnt[i][j] 表示当前位置为i下一个字符为j的位置 倒着遍历字符串即可
预处理一遍之后，每次循环跑的次数就只有strlen(b)
题中给定Σ(strlen(b)) 不大于1e6
而预处理的复杂度为 strlen(a) * 26

所以总共在3e7左右 这是允许的 然后既可以ac了
注意一下下标应该从1开始 或者你从0开始 但是表头位置是一个大于strlen(a)的位置也可以
就是说表头位置不能与字符串a的任一位置重叠(废话)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char s[maxn],a[maxn];
int cnt[maxn][30];
int main(){
    ios::sync_with_stdio(0);
    memset(cnt,-1,sizeof cnt);///初始化都为-1
    cin>>s+1;
    int len=strlen(s+1);
    for(int i=len-1;i>=0;i--){///倒序遍历给定的字符串
        for(int j='a';j<='z';j++){
            cnt[i][j-'a']=cnt[i+1][j-'a'];///把下一个位置的赋值给当前
        }
        cnt[i][s[i+1]-'a']=i+1;///下一个位置的字符覆盖掉
    }
    int m;cin>>m;
    while(m--){
        cin>>a+1;
        int len=strlen(a+1),flag=0,now=0;
        for(int i=1;i<=len;i++){
            if(cnt[now][a[i]-'a']!=-1){///说明存在下一个字符的位置
                now=cnt[now][a[i]-'a'];///位置移动的下一个字符的位置
            }
            else {///不存在下一个字符
                flag=1;
                break;
            }
        }
        if(flag) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
}