本文主要是介绍Pursuing the Happiness,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
分析:由于数据量较小,直接暴力即可,不需要KMP算法,易错点:如果原字符串中有两个子字符串,可以交换第一个子字符串的’h’与第二个子字符串的’a’,如果超过三个子字符串必不能实现仅仅交换两个位置就满足要求,如果只有一个子字符串,就交换’h’和’a’即可,如果没有子字符串,那就必要小心,如果任意交换两个字符,可能会生成“happiness”,例如:“haapiness”,如果交换第一个’h’和第一个’a’,就会生成“happiness”,如果原字符串(不含子字符串)可能会通过交换两个位置上的字符生成子字符串,那么它就一定存在两个’p’和两个’s’,那么我们可以任选’p’或’s’,例如我们选择’p’,找到两个位置上相同的字符’p’,交换这两个位置上的字符,那么换了等于白换,原字符串(不含子字符串)就仍旧不含子字符串,但如果原字符串没有至少两个’p’或’s’,那它就不存在生成子字符串的风险,换句话说,原字符串必不能生成"happiness"。
ac代码:
#include<bits/stdc++.h>
using namespace std;
#define maxx 200001
#define INF 0x3f3f3f3f3fint main()
{string str;cin>>str;int n=str.size();int sum=0;int l,r;for(int i=0; i<n; i++){if(i<n-8&&str[i]=='h'&&str[i+1]=='a'&&str[i+2]=='p'&&str[i+3]=='p'&&str[i+4]=='i'&&str[i+5]=='n'&&str[i+6]=='e'&&str[i+7]=='s'&&str[i+8]=='s'){sum++;if(sum==1){l=i+1;}else if(sum==2){r=i+2+1;}else if(sum>2){break;}}}if(sum==0){l=-1,r=-1;for(int i=0;i<n;i++){if(str[i]=='p'&&l!=-1&&r==-1){r=i+1;}if(str[i]=='p'&&l==-1){l=i+1;}}if(l!=-1&&r!=-1){cout<<"YES"<<endl;cout<<l<<" "<<r<<endl;}else{cout<<"YES"<<endl;cout<<1<<" "<<2<<endl;}}else if(sum>2){cout<<"NO"<<endl;}else{if(sum==1){cout<<"YES"<<endl;cout<<l<<" "<<l+1<<endl;}else if(sum==2){cout<<"YES"<<endl;cout<<l<<" "<<r<<endl;}}return 0;
}
这篇关于Pursuing the Happiness的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!