杭电5311-Hidden String（暴力列举）

落日映苍穹つ 2022-08-18 02:39 14阅读 0赞

# Hidden String #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)**

Total Submission(s): 1688 Accepted Submission(s): 595

Problem Description

Today is the 1st anniversary of BestCoder. Soda, the contest manager, gets a string  s![Image 1][] of length  n![Image 1][]. He wants to find three nonoverlapping substrings  s\[l![Image 1][]1![Image 1][]..r![Image 1][]1![Image 1][]\]![Image 1][],  s\[l![Image 1][]2![Image 1][]..r![Image 1][]2![Image 1][]\]![Image 1][],  s\[l![Image 1][]3![Image 1][]..r![Image 1][]3![Image 1][]\]![Image 1][] that:  
  
1.  1≤l![Image 1][]1![Image 1][]≤r![Image 1][]1![Image 1][]<l![Image 1][]2![Image 1][]≤r![Image 1][]2![Image 1][]<l![Image 1][]3![Image 1][]≤r![Image 1][]3![Image 1][]≤n![Image 1][]  
  
2. The concatenation of  s\[l![Image 1][]1![Image 1][]..r![Image 1][]1![Image 1][]\]![Image 1][],  s\[l![Image 1][]2![Image 1][]..r![Image 1][]2![Image 1][]\]![Image 1][],  s\[l![Image 1][]3![Image 1][]..r![Image 1][]3![Image 1][]\]![Image 1][] is "anniversary".

Input

There are multiple test cases. The first line of input contains an integer  T![Image 1][]  (1≤T≤100)![Image 1][], indicating the number of test cases. For each test case:  
  
There's a line containing a string  s![Image 1][]  (1≤|s|≤100)![Image 1][] 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

暴力列举每一段的长度，把目标字符串分为三段。用strstr函数找到第一次出现字符串的地址

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    char aim[]="anniversary",s[110],s1[110];
    int main()
    {
        int i,j,k,m,flag,n,len,l,loca;
        len=strlen(aim);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",s);
            flag=0;
            for(i=0;i<=8;i++)
            {
                for(j=i+1;j<=9;j++)
                {
                    strcpy(s1,aim);
                    s1[i+1]='\0';
                    l=strstr(s,s1)-s;
                    if(l<0)
                    continue;
                    l+=i+1;
                    
                    strcpy(s1,aim+i+1);
                    s1[j-i]='\0';
                    l=strstr(s+l,s1)-s;
                    if(l<0)
                    continue;
                    l+=j-i;
                    
                    
                    strcpy(s1,aim+j+1);
                    l=strstr(s+l,s1)-s;
                    if(l<0)
                    continue;
                    
                    flag=1;
                    break;
                }
                if(flag)
                break;
            }
            if(flag)
            printf("YES\n");
            else
            printf("NO\n");
        }
        return 0;
     }

[Image 1]: