Pursuing the Happiness

时间:2022-11-07 18:18:05

http://codeforces.com/gym/101341/problem/B

ProblemB. Pursuing the Happiness
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*10^5 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

 

由于数据量较小,不用KMP也可。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int main()
 5 {
 6     int len, i, j, N;
 7     char a[200005], b[15] = "happiness", t;
 8     int re[5], num;
 9     N = 9;
10     num = 0;
11     scanf("%s", a);
12     len = strlen(a);
13     for(i=0; i N-1<len; i  )
14     {
15         for(j=0; j<N; j  )
16         {
17             if(a[i j]!=b[j]) break;
18         }
19         if(j==N)
20         {
21             re[num  ] = i 1;
22             if(num>=3) break;
23         }
24     }
25     if(len < 9)
26     {
27         printf("YESn");
28         printf("%d %dn", 1, 2);
29     }
30     else if(i N-1<len) printf("NOn");
31     else
32     {
33         if(num==0)
34         {
35             t = a[0];
36             a[0] = a[1];
37             a[1] = t;
38 
39             for(i=0; i N-1<len; i  )
40             {
41                 for(j=0; j<N; j  )
42                 {
43                     if(a[i j]!=b[j]) break;
44                 }
45                 if(j==N) break;
46             }
47 
48             if(i N-1>=len)
49             {
50                 printf("YESn");
51                 printf("%d %dn", 1, 2);
52             }
53 
54             else
55             {
56                 printf("YESn");
57                 printf("%d %dn", 1, 3);
58             }
59 
60         }
61         else if(num==1)
62         {
63             printf("YESn");
64             printf("%d %dn", re[0], re[0] 1);
65         }
66         else
67         {
68             printf("YESn");
69             printf("%d %dn", re[0], re[1] 1);
70         }
71     }
72     return 0;
73 }