月月查华华的手机

题意:给定字符串S,以及给定T,可以按照字符出现顺序在S中任意挑取,判断是否可以构成T
例如: S=abcde,T=bd--->输出YES
S=abcde,T=bb--->输出NO
题解:预处理,反向存储第个字符出现的位置
就是 表示从第 位开始, 的每个字母出现的,距离 的最近位置
所以下来进行判断T的时候可以进行跳转 如果 且T串没有判断结束,那么输出NO
例如上述样例解释里面,S=abcde,T=bb, 初始设置为0,第一次跳转到第二个位置,而下来不能跳转了,此时T串没有判断结束,输出NO
时间复杂度:

#include<stdio.h>
#include<string.h>
const int N = 1e6+10;
char str[N];
char s[N];
int next[N][30];
void getnext() {
    memset(next, 0, sizeof(next));//初始化为0代表i位置之后没有该字符
    int len = strlen(str + 1);//长度相应的从1下标开始
    for(int i = len; i >= 1; i --) {
        for(int j = 0; j < 26; j ++) {
            next[i - 1][j] = next[i][j];//str i-1位置继承str i位置的离其它字符最近的位置是第几个
        }
        next[i - 1][str[i] - 'a'] = i;// str i-1位置离str[i]字符的最近位置变为第i个.
    }
}
int main() {
    scanf("%s", str + 1);
    getnext(); //获得序列自动机的next数组
    int T;
    scanf("%d", &T);
    while(T --) {
        int flag = 1;
        scanf("%s", s);
        int len = strlen(s);//模式串长度
        int now = 0;//起点0记录了所有字符的最近位置,从0开始找
        for(int i = 0; i < len; i ++) {
            now = next[now][s[i] - 'a'];
            if(!now) { //如果查到某个字符结果为0说明now位置之后不再有该字符,标记跳出
                flag = 0;
                break;
            }
        }
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
//代码来自:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43266784
//侵删