首页 > 代码库 > BestCoder 1st Anniversary ($) 1002.Hidden String
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)
问题描写叙述
今天是BestCoder一周年纪念日. 比赛管理员Soda有一个长度为的字符串. 他想要知道是否能找到的三个互不相交的子串, , 满足下列条件: 1. 2. , , 依次连接之后得到字符串"anniversary".
输入描写叙述
输入有多组数据. 第一行有一个整数 , 表示測试数据组数. 然后对于每组数据: 一行包括一个仅含小写字母的字符串 .
输出描写叙述
对于每组数据, 假设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\n"); else printf("NO\n"); }return 0; }
BestCoder 1st Anniversary ($) 1002.Hidden String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。