hihocode 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

很多方法写。 因为是恰好 包括 hhio ,一个字符再次出现时，必定是以，该字符后的字符组成hhio,所以更新前面的字符就好。

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <map> using namespace std; int m[6]; int H = 1, h = 0,i=2, o=3; char s[100005]; bool judge(){ if(m[h]&&m[H]&&m[i]&&m[o]) return true; else return false; } int getmin(){ int x = 0x7fffffff; for(int i=0;i<4;i++){ x = min(x,m[i]); } return x; } int getmax(){ int x =-1; for(int i=0;i<4;i++){ x = max(x,m[i]); } return x; } void init(){ m[H] = m[h]=m[i]=m[o]=0; } int main(){ while(scanf("%s",s) != EOF) { init(); int len = strlen(s), ans = 0x7fffffff; for(int j=0;j<len;j++){ if(s[j]=='h'){ if(m[h]==0){ m[h] = j; } else if(m[H]==0){ m[H] = j; } else{ if(m[o] < m[h]) m[o] = 0; if(m[i] < m[h]) m[i] = 0; m[h] = m[H], m[H] = j; } } if(s[j]=='i'){ if(m[H]<m[i]) m[H] = 0; if(m[h]<m[i]) m[h] = 0; if(m[o]<m[i]) m[o] = 0; m[i] = j; } if(s[j]=='o'){ if(m[H]<m[o]) m[H] = 0; if(m[h]<m[o]) m[h] = 0; if(m[i]<m[o]) m[i] = 0; m[o] = j; } if(judge()){ int x = getmin(); int y = getmax(); x = y-x+1; ans = min(ans,x); } } if(ans == 0x7fffffff) printf("-1\n"); else printf("%d\n",ans); } return 0; }