每日一题

第一眼看见这个题以为是KMP问题，后来发现自己错了，子串和子序列不同！#……&（）……#
相比于KMP问题有很多相似之处，如果我们用一个一个比较字符的话，时间复杂度是N * N
我们用一个 ne 数组 来记录位置关系， ne[i][j]代表 在第 i 个字符 下一个 i + 1 字符最近的位置，我们就一直看这个位置是不是为空，不为空那么我们往后跳，为空的话就直接结束。在这里求 ne 数组 用 从后往前计算，last 为辅助数组，是最近的字符出现的位置。
重点来了，敲黑板
重点来了，敲黑板
重点来了，敲黑板
自己犯的一个致命错误，在调用函数是一定要记得加 () 啊
自己犯的一个致命错误，在调用函数是一定要记得加 () 啊
自己犯的一个致命错误，在调用函数是一定要记得加 () 啊

#include<bits/stdc++.h>
#define pr printf
#define sc scanf
#define fur(i,a,b) for(int i = a; i<= b ;i++)
#define fdr(i,a,b) for(int i = a; i>= b ;i--)
using namespace std;
typedef long long ll;
const int N = 1e6 + 10 ;
int ne[N][30];
char str[N],mo[N];
int last[30];
void get_ne()
{
    memset(last,-1,sizeof (last));
    int l = strlen(str);
    for(int i = l - 1 ; i >= 0 ;i--)
    {
        for(int k = 0 ; k < 26 ; k ++)
        {
            ne[i][k] = last[k];
        }
        last[str[i] - 'a' ] =  i ;
    }
}
bool work()
{
    int l = strlen(mo);
    int i = last[mo[0] - 'a'];
    if(i == -1)return false;
    for(int j = 1 ; j < l ; j++)
    {
        i = ne[i][mo[j] - 'a' ];
        if(i == -1)return false;
    }
    return true;
}
int main()
{
    freopen("in.txt","r",stdin);
    scanf("%s",str);
    get_ne();
    int T ;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",mo);
        if(work())puts("Yes");
        else puts("No");
    }
    return 0;
}