月月查华华的手机 预处理优化+暴力

题意：在主串中寻找子序列

思路：字符串长度都来到了1e6 暴力肯定超时 我们可以先预处理一个next数组来表示主串当前第i个字符到任意26个字母下一个位置是在哪 然后模式串根据next数组匹配 复杂度为 "图片标题")

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6+5;
const int M = 2e5+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;

int next[N][30];///表示主串当前第i个字符到任意26个字母下一个位置是在哪
int last[30];///上一次字母出现的位置
char a[N],b[N];

void db()
{
    int len = strlen(a);
    memset(last, -1, sizeof(last));///初始化为-1 代表没有出现过

    for(int i = len - 1;i >= 0;i --)///倒序遍历之后last数组就是第一次字母出现的位置了
    {
        for(int j = 0;j < 26;j ++)
        {
            next[i][j] = last[j];
        }

        last[a[i] - 'a'] = i;
    }
}


int main()
{
    scanf("%s",a);

    int n;

    scanf("%d",&n);

    db();

    while(n --)
    {
        scanf("%s",b);

        int pos = last[b[0]-'a'];

        if(pos == -1)///首字母没有直接GG 这样可以不量字符串b的长度 扣点常数
        {
            printf("No\n");
            continue;
        }

        bool flag = 1;
        int lenb = strlen(b);

        for(int j = 1;j < lenb;j ++)
        {
            pos = next[pos][b[j]-'a'];///直接跳跃到下一个字母的位置

            if(pos == -1)
            {
                flag = 0;
                break;
            }
        }

        if(flag)
            printf("Yes");
        else
            printf("No");

        printf("\n");
    }
    return 0;
}