Problem Description

Today is the 1st anniversary of BestCoder. Soda, the contest manager, gets a string s of length n. He wants to find three nonoverlapping substrings s[l1..r1], s[l2..r2], s[l3..r3] that:
1. 1≤l1≤r1<l2≤r2<l3≤r3≤n
2. The concatenation of s[l1..r1], s[l2..r2], s[l3..r3] is "anniversary".

 

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤100), indicating the number of test cases. For each test case:
There's a line containing a string s (1≤|s|≤100) consisting of lowercase English letters.

 

Output

For each test case, output "YES" (without the quotes) if Soda can find such thress substrings, otherwise output "NO" (without the quotes).

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define SL(x) scanf("%lld",&x)

#define PI(x) printf("%d",x)

#define PL(x) printf("%lld",x)

#define P_ printf(" ")

#define T_T while(T--)

typedef long long LL;

const int INF=0x3f3f3f3f;

char s[110];

char a[20]="anniversary";

int ans,len;

void dfs(int p1,int p2,int num){

	if(num>3)return;

	if(p2>=11){

	//	printf("%d\n",num);

		ans=1;return;

	}

//	printf("%d\n",len);

//	if(p1>len)return;

	int x,y;

	for(int i=p1;i<len;i++){

	x=i;y=p2;

		while(s[x]==a[y])x++,y++;

	//	printf("%d",y);

		 if(x!=i)dfs(x,y,num+1);

		 else dfs(x+1,y,num+1);

	}

}

int main(){

	int T;

	SI(T);

	T_T{

		ans=0;

		scanf("%s",s);

		len=strlen(s);

		dfs(0,0,0);

		if(ans)puts("YES");

		else puts("NO");

	}

	return 0;

}

package com.lanqiao.week1;

import java.util.Scanner;

public class hdu5311 {

    private static Scanner cin = null;

    static{

        cin = new Scanner(System.in);

    }

    static char[] mstr = "anniversary".toCharArray();

    static boolean ans;

    private static void dfs(int m, int s, int cnt, char[] str){

        //System.out.println(m + "-->" + s + "-->" + cnt);

        if(cnt > 3)return;

        if(m >= mstr.length){

            ans = true;

            return;

        }

        for(int i = s; i < str.length; i++){

            int si = i, mi = m;

            while(mi < mstr.length && si < str.length && mstr[mi] == str[si]){

                mi++;

                si++;

            }

            if(si != i){

                dfs(mi, si, cnt + 1, str);

            }

        }

    }

    public static void main(String[] args) {

        int T;

        T = cin.nextInt();

        while(T-- > 0){

            String str = cin.next();

            ans = false;

            dfs(0, 0, 0, str.toCharArray());

            if(ans){

                System.out.println("YES");

            }else{

                System.out.println("NO");

            }

        }

    }

}