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

这道题 千万别看错题误以为是kmp，其实不是的！！
注意题目说的是子序列而不是子串，所以kmp不行
那么这道题该怎么做呢？
仔细想想，既然它给定了你一开始那个s字符串，就是待匹配的字符串，那么我们要做的就是去预处理一下。
用一个dp数组，dp[i][j]代表第i个字符后面最近的'a'+j字符的位置，我们从后往前跑一遍，用last数组记录当前的26个字母位置（没有的话就是-1），这样的话，我们只要边从后往前遍历s字符串，再一边跟新last数组就OK啦。
最后对于给定的字符判断一下，对于每一个检测字符如果找不到下一个字符就返回false，否则代表能找到返回true。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N],t[N];
int n,last[26],ne[N][26];  //ne[i][j]表示第i个字母后面最近的'a'+j的位置

void init()
{

    memset(last,-1,sizeof(last));
    int l=strlen(s);

    for(int i=l-1;i>=0;i--)
    {

        for(int j=0;j<26;j++)
        {
            ne[i][j]=last[j];
        } 
        last[s[i]-'a']=i ;   //更新当前的last数组
    }
}

bool ok()
{
    int cur=last[t[0]-'a'];
    if(cur==-1) return false;
    for(int i=1;i<strlen(t);i++)
    {
        cur=ne[cur][t[i]-'a'];
        if(cur==-1) return false;
    }
    return true;
}
int main()
{
    scanf("%s",s);
    init();
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",t);
        if(ok()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}