首页 > 其他 > 详细

Subsequence (暴力搜索)

时间:2019-04-22 20:23:28      阅读:85      评论:0      收藏:0      [点我收藏+]

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 N1K1?<K2?<K3?<?<Km?N and Ski=TiS_{k_i} = T_iSki??=Ti?, (1≤i≤m)(1 \le i \le m)(1im), then TiT_iTi? is a subsequence of SSS.

Input

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

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

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

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 <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f;
const  ll linf  =1LL<<50;
const int maxn = 1e5+8;
string s, miao;
int n;
int main()
{
    cin>>s;
    int l = s.size();
    cin >> n;
    while(n--)
    {
        cin>>miao;
        int len = miao.size();
        int ga = 0;
        for(int i = 0; i<l; i++)
        {
            if(miao[ga] == s[i])
            {
                ga++;
            }
            if(ga == len)break;
        }
        if(ga == len)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

 

Subsequence (暴力搜索)

原文:https://www.cnblogs.com/RootVount/p/10752507.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!