BestCoder 1st Anniversary ($) 1002.Hidden String
Hidden String
Accepts: 437
Submissions: 2174
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
問題の説明
説明の入力
出力の説明
入力サンプル
出力サンプル
分析:「anniversary」をセグメント化し、暴力的に探せばいい.
タイトルリンク:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=610&pid=1002
コードリスト:
Accepts: 437
Submissions: 2174
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
問題の説明
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".
説明の入力
.
T
(1≤T≤100)
, . :
s
(1≤|s|≤100)
.
出力の説明
, Soda , "YES", "NO".
入力サンプル
2
annivddfdersewwefary
nniversarya
出力サンプル
YES
NO
分析:「anniversary」をセグメント化し、暴力的に探せばいい.
タイトルリンク:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=610&pid=1002
コードリスト:
#include<queue>
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int get_index(string ss,string s,int p){ //
int slen=s.size();
int sslen=ss.size();
for(int i=p;i<=slen-sslen;i++){
int first=1;
for(int j=0;j<sslen;j++){
if(ss[j]==s[i+j])
continue;
else{
first=0;
break;
}
}
if(first){ return i+sslen; }
}return -1;
}
bool judge(string s1,string s2,string s3,string s){
int pp=get_index(s1,s,0);
if(pp==-1) return false;
pp=get_index(s2,s,pp);
if(pp==-1) return false;
pp=get_index(s3,s,pp);
if(pp==-1) return false;
return true;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
string s;
string str="anniversary";
cin>>s;
string s1="",s2,s3;
bool ok=false;
for(int i=1;i<=9;i++){ //
s1+=str[i-1];
for(int j=i;j<=9;j++){
s2="";s3="";
for(int k=i;k<=j;k++) s2+=str[k];
for(int k=j+1;k<11;k++) s3+=str[k];
if(judge(s1,s2,s3,s)){
ok=true;
break;
}
}if(ok) break;
}
if(ok) printf("YES
");
else printf("NO
");
}return 0;
}