HDOJ 5311-Hidden String【深搜】

妖狐艹你老母 2022-08-18 02:36 55阅读 0赞

# Hidden String #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)  
Total Submission(s): 1677 Accepted Submission(s): 589**

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

2
    annivddfdersewwefary
    nniversarya

Sample Output

YES
    NO

解题思路

因为这个题中长度比较小可以暴力搞一下，利用深搜写在判断里判断是否满足段数大于三，然后继续深搜。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int len,len1;
    char map[100000];
    char moxing[20]="anniversary";
    bool f(int x,int y,int ci)
    {
    	int i;
    	if(ci<=3&&y>=len1)
    	{
    		return true;
    	}
    	else if(ci>3)
    	{
    		return false;
    	}
    	for(i=x;i<len;i++)
    	{
    		int wc,wcnm;
    		wc=i,wcnm=y;
    		while(wc<len&&wcnm<len1&&map[wc]==moxing[wcnm])
    		{
    			wc++;
    			wcnm++;
    		}
    		if(wc>i&&f(wc,wcnm,ci+1))
    		{
    			return true;
    		}	
    	}
    	return false;
    }
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%s",map);
    		len=strlen(map);
    		len1=strlen(moxing);
    		bool cnm=f(0,0,0);
    		if(cnm==true)
    		printf("YES");
    		else
    		printf("NO");
    		printf("\n");
    	}
    	return 0;
    }