2018暑期SICNU-ACM组集训报告（5）

题目：

Input file: standard input
Output file: standard output
Time limit: 2 seconds
Memory limit: 256 megabytes
Mike wants to find a substring «happiness» in the string s, but Constantine cannot allow this and decided
to hinder him. He is planning to swap two characters on two different positions in the string s so that
Mike wouldn’t be able to find what he looks for. Which two characters Constantine should swap?
Input
The only line contains from 2 to 2 · 105
lowercase Latin letters — the string s, in which Mike wants to
find a substring «happiness».
Output
If Constantine succeeds in achieving his goal, in the first line output «YES» without quotes. In the second
line output two distinct integers separated by a space — the positions of characters in the string s, which
Constantine should swap. Positions in the string are numbered from one. If there are several possible
answers, output any of them.
If for any choice of Constantine Mike still would be able to find a substring «happiness», in the only line
output «NO» without quotes.
Examples
standard input
pursuingthehappiness
standard output
YES
15 18
standard input
happinessformehappinessforyouhappinessforeverybodyfreeandletnoonebeleftbehind
standard output
NO

原题链接：http://codeforces.com/gym/101341/problem/B

题意：
看似很复杂的题目实际上读懂之后只需要明白一点，交换字符串中的两个位置能否不构成“happiness”
值得注意的是，若串中原不含模式串时，这时随意交换可能反而会形成模式串。
那么原串中若有相同字符，互换即可。若没有，交换头两个字符即可保证不会形成模式串。
AC代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int main(int argc, char const *argv[])
{
    string s,ss;
    ss="happiness";
    cin>>s;
    long long i=0,k,l;
    int cnt=0;
    for(;;)
    {
        if(cnt==0)
        {
            i=s.find(ss);
            if (i!=string::npos)
            {
                cnt++;
                k=i;
            }
            else
                break;
        }
        else
        {
            i=s.find(ss,i+ss.size());
            if (i!=string::npos)
            {
                cnt++;
                if(cnt==2)
                {
                    l=i;
                }
            }
            else
                break;
        }
    }
    if (cnt==0)
    {
        printf("YES\n");
        long long m,n,a=0;
        for(m=0;m<s.size();m++)
        {
            for(n=m+1;n<s.size();n++)
            {
                char s1;
                s1=s[m];
                s[m]=s[n];
                s[n]=s1;
                if(s.find(ss)==string::npos)
                {
                    printf("%lld %lld\n",m+1,n+1);
                    a=1;
                    break;
                }
            }
            if(a==1)
                break;
        }
    }
    else if(cnt==1)
    {
        printf("YES\n");
        long long m,n,a=0;
        for(m=k;m<k+ss.size();m++)
        {
            for(n=m+1;n<k+ss.size();n++)
            {
                char s1;
                s1=s[m];
                s[m]=s[n];
                s[n]=s1;
                if(s.find(ss)==string::npos)
                {
                    printf("%lld %lld\n",m+1,n+1);
                    a=1;
                    break;
                }
            }
            if(a==1)
                break;
        }
    }
    else if(cnt==2)
    {
        printf("YES\n");
        long long m,n,a=0;
        for(m=k;m<k+ss.size();m++)
        {
            for(n=l;n<l+ss.size();n++)
            {
                char s1;
                s1=s[m];
                s[m]=s[n];
                s[n]=s1;
                if(s.find(ss)==string::npos)
                {
                    printf("%lld %lld\n",m+1,n+1);
                    a=1;
                    break;
                }
            }
            if(a==1)
                break;
        }
    }
    else
        printf("NO\n");
    return 0;
}