Subsequence(判断子序列)

Give a string SSS and NNN string TiT_iTi​ , determine whether TiT_iTi​ is a subsequence of SSS.

If ti is subsequence of SSS, print YES,else print NO.

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

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

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

Then next nnn lines,every line is a string TiT_iTi​, length(TiT_iTi​) ≤1000\le 1000≤1000
Output

Print NNN lines. If the iii-th TiT_iTi​ is subsequence of SSS, print YES, else print NO.
样例输入

abcdefg
3
abc
adg
cba

样例输出

YES
YES
NO

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>

using namespace std;
int p[30][1100000];
char st[110000];
int main()
{
    int n;
    memset(p,0,sizeof(p));
    scanf("%s",st);
    scanf("%d",&n);
    int i,j;
    int len1 = strlen(st);
    for(i=0; i<len1; i++)
    {
        int t = st[i] - 'a';
        p[t][i] = 1;  //记录下某个字母在的位置
    }
    while(n--)
    {
        char b[1100];
        scanf("%s",b);
        int cnt = 1;
        int x = -1;
        int len2 = strlen(b);
        for(i=0; i<len2; i++)
        {
            for(j=x+1; j<len1; j++)    
            {
                if(p[b[i]-'a'][j]==1)
                {
                    x = j;
                    break;
                }
            }
            if(j==len1)  //循环正常结束，说明不是st的子序列
            {
                cnt = 0;
                break;
            }
        }
        if(cnt)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}