月月查华华的手机 （序列自动机）

月月查华华的手机

https://ac.nowcoder.com/acm/problem/23053
来源：牛客网

题目大意：
给出一个字符串S，然后k次查询，问字符串t是否是s的子序列，是的话输出yes，反之输出no。

因为n和s都是1e6，暴力的话必然会超时，所以用到了序列自动机
就是建立一个next[i][j]数组，记录 i 位置之后【j-'a'】字母第一次出现的位置然后匹配即可。

该题代码：

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define INT 9654234
using namespace std;
const int maxn = 1e6+5;
int n,m,x,t;
char s[maxn],str[maxn];
int nextt[maxn][28];

void solve(){
    n=strlen(s+1);
    for(int i=n;i>=1;i--){
        for(int j=0;j<26;j++){
            nextt[i-1][j]=nextt[i][j];
        }
        nextt[i-1][s[i]-'a']=i;
    }
}

bool check(){
    m=strlen(str+1);
    x=0;
    for(int i=1;i<=m;i++){
        x=nextt[x][str[i]-'a'];
        if(!x) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s+1;
    solve();
    cin>>t;
    while(t--){
        cin>>str+1;
        if(check()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}