B. Hidden String

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=610&pid=1002

Description

今天是BestCoder一周年纪念日. 比赛管理员Soda有一个长度为n的字符串s. 他想要知道能否找到s的三个互不相交的子串s[l1..r1], s[l2..r2], s[l3..r3]满足下列条件:

  1. 1≤l1≤r1<l2≤r2<l3≤r3≤n

  2. s[l1..r1], s[l2..r2], s[l3..r3]依次连接之后得到字符串"anniversary".

Input

输入有多组数据. 第一行有一个整数T (1≤T≤100), 表示测试数据组数. 然后对于每组数据:

一行包含一个仅含小写字母的字符串s (1≤|s|≤100).

Output

对于每组数据, 如果Soda可以找到这样三个子串, 输出"YES", 否则输出"NO".

Sample Input

2

annivddfdersewwefary

nniversarya

Sample Output

YES
NO

HINT

题意

题解：

DFS

代码

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <ctime>

 #include <iostream>

 #include <algorithm>

 #include <set>

 #include <vector>

 #include <sstream>

 #include <queue>

 #include <typeinfo>

 #include <fstream>

 #include <map>

 #include <stack>

 typedef __int64 ll;

 using namespace std;

 typedef __int64 ll;

 const int inf = (int)1E9+;

 inline ll read()

 {

     ll x=,f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 //*******************************

 int T;

 char s[];

 char s1[] = "anniversary";

 bool dfs(int num,int k,int i)

 {

     if(num >= ) return ;

     while(s[k] != '\0')

     {

         if(s[k] == s1[i])

         {

             k++;

             i++;

             if(dfs(num+,k,i)) return true;

             if(s1[i] == '\0')return true;

         }

         else

         {

             break;

         }

     }

     for(; s[k] != '\0'; ++k)

     {

         if(s[k] == s1[i])

         {

             if(dfs(num+,k,i)) return true;

         }

     }

     return false;

 }

 int main()

 {

     cin>>T;

     while(T--)

     {

         scanf("%s",s);

         int flag=;

         for(int i=; s[i]!='\0'; ++i)

         {

             if(s[i]=='a')

             {

                 flag=dfs(,i,);

                 if(flag) break;

             }

         }

         if(flag) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

巴特西

BestCoder 1st Anniversary B.Hidden String DFS

B. Hidden String

题目连接

Description

HINT

最新文章

热门文章