题解 | #月月查华华的手机#

本题我采用了序列自动机的方法，设置一个nxt[MAXLEN][30]数组，此数组的行与字符串母串的字符一一对应，列代表26个英文字母，nxt[i][j]=0表示字符'a'+j在字符t[i]后不存在，nxt[i][j] > 0，其数值表示字符'a'+j在字符t[i]的坐标。 注意：不要使用memset重置子串，会超时，来自于菜鸡的血泪

#include <iostream>
using namespace std;
#include <string.h>
#include <stdlib.h>

const int MAXLEN = 1e6 + 5;
char s[MAXLEN]; //存放输入的字符串母串
int nxt[MAXLEN][26]; //横坐标分别对应字符串s的每一个字符，纵坐标是26个字母，数组存放的是距离当前字符最近的后一个字符的位置
char t[MAXLEN]; //记录字串


int main(void)
{
    scanf("%s", s); //从下标1的位置开始输入字符串
    int s_len = strlen(s);

    //将当前字符串中每个字符所在位置传入next数组
    //分别推出每个元素的值
    for(int i = s_len-1; i >= 0; i--)
    {
        nxt[i][s[i]-'a'] = i+1;
        for(int j = 0; j < 26; j++)
        {
            if(0 == nxt[i][j])
                nxt[i][j] = nxt[i+1][j];
        }
    }
    
    int  n;
    scanf("%d", &n);

    while(n--)
    {
        scanf("%s", t);
        int t_len = strlen(t);
        int pos = 0; //指向nxt数组的指针
        bool flag = true;
        //遍历字串，在nxt数组中找对应位置
        for(int i = 0; i < t_len; i++)
        {
            //如果字符找不到
            pos = nxt[pos][t[i]-'a'];
            if(0 == pos)
            {
                flag = false;
                break;
            }
        }

        if(true == flag) printf("Yes\n");
        else printf("No\n");
    }
    
    return 0;
}