【每日一题】月月查华华的手机 (序列自动机)

Solution
判断子序列的话让我想起了上次cf的一道C题，哪一场已经忘了，但是做法的话不外乎两种：
1.二分查找
2.序列自动机
因为上次是二分过的，这次就写一下序列自动机。
nexts[i][j]表示的是i位置之后j字符在原串中的索引，那么预处理nexts数组之后，直接对输入的每个串遍历判断 i 位置之后的 s[i] 字符是否存在即可。
最后讲一下预处理，因为是i位置之后的索引，所以要逆序遍历原串,
遍历 j = ' a ' -> ' z '，nexts[i-1][j] = nexts[i][j] ，
特殊地 nexts[ i-1 ][ c[i]-'a' ]=i。

Code

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }

const int manx=1e6+5;

char s[manx],c[manx];
ll nexts[manx][26];

int main()
{
    cin>> s+1;
    ll n=strlen(s+1);
    for(int i=n;i;i--){
        for(int j=0;j<26;j++)
            nexts[i-1][j]=nexts[i][j];
        nexts[i-1][s[i]-'a']=i;
    }
    ll p=read();
    while(p--){
        cin>>c;
        ll n=strlen(c);
        ll flag=1;
        for(int i=0,now=0;i<n;i++){
            now=nexts[now][c[i]-'a'];
            if(!now){
                flag=0;
                break;
            }
        }
        if(flag) put1();
        else put2();
    }
    return 0;
}