2019南昌大学邀请赛 M. Subsequence 序列自动机

Give a string SS and NN string T_iTi , determine whether T_iTi is a subsequence of SS.

If ti is subsequence of SS, print ​​YES​​​,else print ​​NO​​.

If there is an array \lbrace K_1, K_2, K_3,\cdots, K_m \rbrace{K1,K2,K3,⋯,Km} so that 1 \le K_1 < K_2 < K_3 < \cdots < K_m \le N1≤K1<K2<K3<⋯<Km≤N and S_{k_i} = T_iSki=Ti, (1 \le i \le m)(1≤i≤m), then T_iTi is a subsequence of SS.

Input

The first line is one string SS,length(SS) \le 100000≤100000

The second line is one positive integer N,N \le 100000N,N≤100000

Then next nn lines,every line is a string T_iTi, length(T_iTi) \le 1000≤1000

Output

Print NN lines. If the ii-th T_iTi​ is subsequence of SS, print ​​YES​​​, else print ​​NO​​.

样例输入复制

abcdefg 3 abc adg cba

样例输出复制

YES YES NO

题意：给定序列A，和N个序列Bi，若Bi是A的一个子序列（不一定连续）。

分析：

序列自动机模板题

nex[maxn][26]:表示第i个字符后面第一次出现字符j（a-z用0-25表示）的位置。

我们从后往前求，now[j]:字符j从后往前数最晚出现的位置（now数组初始化为-1）

对于每个i，我们都用now[0-25]来更新nex[i][0-25]的值

每经过一个i，我们就更新now数组~使得now数组表示的是最新的状态

但是两个字符串开始的字符是相等的，就没法判断，因为nex[0][j]表示的是0位置后的第一个出现j的位置。所以就要先判断

int loc=now[s[0]-'a']

若loc不为-1，
 

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef pair<int,int>P;
const int INF=0x3f3f3f3f;
const int N=1000010,mod=32767;
char s[N],p[N];
int nex[N][30],now[N];
//nex[i][j]:=表示第i个字符后面第一次出现字符j（a-z用0-25表示）的位置。
//我们从后往前求，now[j]:=字符j从后往前数最晚出现的位置（now数组初始化为-1）
void init()
{
    memset(now,-1,sizeof(now));
    int len=strlen(s);
    for(int i=len-1; i>=0; i--)
    {
        for(int j=0; j<26; j++)
        {
            nex[i][j]=now[j];
        }
        now[s[i]-'a']=i;
    }
}

int main()
{
    int n,len,loc,flag;
    scanf("%s",s);
    init();
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%s",p);
        len=strlen(p);
        loc=now[p[0]-'a'];
        if(loc==-1)
            printf("NO\n");
        else
        {
            flag=0;
            for(int i=1; i<len; i++)
            {
                loc=nex[loc][p[i]-'a'];
                if(loc==-1)
                {
                    flag=1;
                    break;
                }
            }
            if(!flag)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
}