#1485 : hiho字符串
时间限制:
10000ms
单点时限:
1000ms
内存限制:
256MB
描述
如果一个字符串恰好包含2个'h'、1个'i'和1个'o',我们就称这个字符串是hiho字符串。
例如"oihateher"、"hugeinputhugeoutput"都是hiho字符串。
现在给定一个只包含小写字母的字符串S,小Hi想知道S的所有子串中,最短的hiho字符串是哪个。
输入
字符串S
对于80%的数据,S的长度不超过1000
对于100%的数据,S的长度不超过100000
输出
找到S的所有子串中,最短的hiho字符串是哪个,输出该子串的长度。如果S的子串中没有hiho字符串,输出-1。
happyhahaiohell样例输出
5
给一个长度100000的字符串,求恰好包含2个h,1个o,1个i的子串的最小长度
今天比赛的第一个题,用尺取法贪心解决的,我自己都不想看我写的代码,写的太挫了,很多可以优化的地方,反正交上去A了就再也不看这代码了,再也不看了。。。。
用4个标记存一下hiho的位置,控制好l和r,然后就是取啦。。。
#include <iostream> #include <stdio.h> #include <math.h> #include <stdlib.h> #include <string> #include <string.h> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <stack> using namespace std; char S[100009]; int main(){ while(scanf("%s",S)!=EOF){ int len=strlen(S); int ans=999999; int l=0; int r=0; int po=-1,pi=-1,ph1=-1,ph2=-1; int num_h=0; for(int i=0;i<len;i++){ if(S[i]=='h'){ if(num_h==0){ ph1=i; num_h++; //if(l==-1)l=i; r=i; //r=i; } else if(num_h==1){ ph2=i; num_h++; r=i; } else{ l=ph1+1; ph1=ph2; ph2=i; r=i; } if(pi<l)pi=-1; if(po<l)po=-1; //r=i; if(pi>=l&&pi<=r&&po>=l&&po<=r&&num_h==2){ l=min(pi,po); l=min(l,ph1); ans=min(ans,r-l+1); } } if(S[i]=='o'){ if(po==-1){ r=i; po=i; } else{ r=i; l=po+1; po=i; } if(pi<l)pi=-1; if(ph1<l&&ph1!=-1){ ph1=-1; num_h--; ph1=ph2; ph2=-1; } if(ph1<l&&ph1!=-1){ ph1=-1; num_h--; } if(pi>=l&&pi<=r&&ph1>=l&&ph1<=r&&num_h==2&&po>=l){ l=min(pi,po); l=min(l,ph1); ans=min(ans,r-l+1); } } if(S[i]=='i'){ if(pi==-1){ r=i; pi=i; } else{ r=i; l=pi+1; pi=i; } if(po<l)po=-1; if(ph1<l&&ph1!=-1){ ph1=-1; num_h--; ph1=ph2; ph2=-1; } if(ph1<l&&ph1!=-1){ ph1=-1; num_h--; } if(pi>=l&&pi<=r&&ph1>=l&&ph1<=r&&num_h==2&&po>=l&&po<=r){ l=min(pi,po); l=min(l,ph1); ans=min(ans,r-l+1); } } } if(ans==999999)cout<<-1<<endl; else cout<<ans<<endl; //cout<<ans<<endl; } return 0; }