Well, here are some hints:
1. Use DFA. If you do'nt know what it is, visit this page http://en.wikipedia.org/wiki/Deterministic_finite_automaton (pay attention to the table of states)

2. use getc() instead of cin>>ch or cin.getch() or whatever you use (for C++/C only)

3. Try this:
3
outputoutputinputon

inputone

Edited by author 13.06.2007 17:36

There only 10 situations!!!!!
//1. in
//2. input
//3. inputon
//4. inputone

//5. out
//6. output
//7. outputon
//8. outputone

//9. puton
//10. one

Check their in inverse order.

   bool check(char const* s){
        while(*s != '\n'){
               if (s == "one") s += 3;
              // there s == "one" only pseudocode, you may check
             //  as memcmp(s, "one",3) == 0
               else  // ......

               //.............

               // 10 times else
               else if (s == "in") s +=2;
               else
                  return false;
         }
        return true;
   }

I just cin every string and then solve using it. 0.156 accepted

delete

Edited by author 04.10.2020 16:38

At first,I got wa on test1,like many other authors.But later,I found it!
All in one sentence,test the data below:


1
inputon

outputon

YES

Edited by author 28.08.2018 23:32

I always get ML, and i cant understand what sould i do?

I tried to use Scanner and BufferedReader.

Please tell me method to solve this.

If in the line "outputon", this does not mean that you need to put "out" and "puton", since sometimes you can put "output" and "one".

Сheck out this test:
1
outputone
Answer : "YES"

Perhaps this will help you.

Edited by author 01.11.2017 18:28

Edited by author 01.11.2017 18:29

check this.
http://acm.timus.ru/rating.aspx?space=1&num=1102

Don't use cin(TL1) and getc(WA1), use scanf and get AC:

char s[(int)1e7];
scanf("%s", &s);
length = strlen(s);

#include<iostream.h>
#include<string.h>
using namespace std;
int main()
{
    int number;
    cin>>number;
    string s;
    int i=0;
    for(;i<number;i++)
    {
       cin>>s;
       std::size_t find=s.find("puton");
       std::size_t find1=s.find("one");
       if((find != std::string::npos)||(find1 != std::string::npos))
       cout<<"YES\n";
       else
       cout<<"NO";
       s.clear();
    }
    //system("pause");
    return 0;
}

I don't know why my O(N) solution is crashing on 1st test.

Code on C++11: http://ideone.com/BZIoKv

Maybe I don't know some disadvantages of C++? Or it's my algorithm error?

My solution using DFA works half a second.
In the ranking of many solve the problem for 0.1 second. How?

Help please)! Why WA 1? I check my Pascal code and the answer is right!

I read 3 chars and run the follow DFA:
                one on in/out put
lost:
empty:
in/out:
input/output:
put:

here is my code:

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <string>

using namespace std;

inline bool good(char C)
{
    return (C >= 'a' && C <= 'z');
}

int a[5][4] = {{0, 0, 0, 0},
               {1, 0, 2, 4},
               {1, 0, 2, 3},
               {1, 1, 2, 4},
               {0, 1, 0, 0}};

char c[3];

bool get_ans()
{
    int n_u = 0, pos = 1;

    if (!good(c[2])) {
        return (c[0] == 'i' && c[1] == 'n');
    }

    bool n2 = 0;
    while (true)
    {
        if (pos == 0) return 0;
        if (n2) return (pos != 0 && pos != 4);

        c[0] = c[n_u % 3];

        for (int i = 3 - n_u; i < 3; i++)
        {
            c[i] = getc(stdin);
            if (!good(c[i])) {
                if (i == 0) return (pos != 0 && pos != 4);
                if (i == 1) return 0;
                n2 = 1;
                break;
            }
        }


        if (!n2 && c[0] == 'o' && c[1] == 'n' && c[2] == 'e') {
            pos = a[pos][0];
            n_u = 3;
            continue;
        }

        if (c[0] == 'o' && c[1] == 'n') {
            pos = a[pos][1];
            n_u = 2;
            continue;
        }

        if (!n2 && c[0] == 'o' && c[1] == 'u' && c[2] == 't') {
            pos = a[pos][2];
            n_u = 3;
            continue;
        }

        if (c[0] == 'i' && c[1] == 'n') {
            pos = a[pos][2];
            n_u = 2;
            continue;
        }

        if (!n2 && c[0] == 'p' && c[1] == 'u' && c[2] == 't') {
            pos = a[pos][3];
            n_u = 3;
            continue;
        }
        return 0;
    }
}

int main()
{
//    assert(freopen("inp.in", "r", stdin) != NULL);

    int n; assert(scanf("%d", &n) == 1);

    c[0] = getc(stdin);

    for (int i = 0; i < n; i++)
    {
        bool ok = 0;
        c[0] = getc(stdin);

        if (good(c[0])) {
            c[1] = getc(stdin);
            if (good(c[1])) {
                c[2] = getc(stdin);
                ok = get_ans();
            } else {
                ok = 0;
            }
        }

        if (ok) printf("YES\n");
        else printf("NO\n");
    }
}

Edited by author 10.12.2013 21:13

Edited by author 10.12.2013 21:15

Edited by author 10.12.2013 21:22

"(one|puton|out|output|in|input)+"
it has simple solve using regexp, but i got ML 1. How to read correctly?

Edited by author 18.09.2013 18:24

May be this tests will help to some others.
When my prog passed all of them , I'v get AC.

12
putone
inputon
outputoutputinputon
inputone
putin
outputin
puton
inonputin
oneputonininputoutoutput
oneininputwooutoutput
outpu
utput

Answers:
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
NO
NO

#include <iostream>
#include <cstdlib>
#include <stdio.h>
//#pragma comment(linker, "/STACK:16777216")


using namespace std;

int flag=0;
int flag1=0;
char *a = new char [10000001];


  int f(int pos,int flag,int n){
    int l=0;
    if ((pos==n+1) && (flag==1)) {std::cout<<"YES"<<endl; flag1=1; return 0;}
    if ((pos==n+1) && (flag==0)) {}
    else if (pos<=n){
    {if ((a[pos]=='o') && (a[pos+1]=='u') && (a[pos+2]=='t') && (a[pos+3]=='p') && (a[pos+4]=='u') && (a[pos+5]=='t')) {f(pos+6,1,n);l=1;}
    if ((a[pos]=='i') && (a[pos+1]=='n') && (a[pos+2]=='p') && (a[pos+3]=='u') && (a[pos+4]=='t')) {f(pos+5,1,n);l=1;}
    if ((a[pos]=='p') && (a[pos+1]=='u') && (a[pos+2]=='t') && (a[pos+3]=='o') && (a[pos+4]=='n')) {f(pos+5,1,n);l=1;}
    if ((a[pos]=='o') && (a[pos+1]=='u') && (a[pos+2]=='t')) {f(pos+3,1,n);l=1;}
    if ((a[pos]=='o') && (a[pos+1]=='n') && (a[pos+2]=='e')) {f(pos+3,1,n);l=1;}
    if ((a[pos]=='i') && (a[pos+1]=='n')) {f(pos+2,1,n);l=1;}
    if (l==0) {}
    }}
}



int main()
{
    int k=0,n=0,j=0;
    int i=0;
    std::cin>>k;
    char c;
    for (j=1;j<=k+1;j++)
    {
        i=0; flag1=0;
        while (((c = getchar()) != '\n') ) {a[i]=c;i++;}
        n=i-1;

       if (n>0) {
                 f(0,0,n);
                  if (flag1==0) std::cout<<"NO"<<endl;}

    }




}

Edited by author 11.07.2013 23:48

Edited by author 11.07.2013 23:49

For those who solved this in Java with a lots of tricks. Thumbs up!

Take a look at P1148. It's really similar. E.g. simple DP problem, which becomes stick in ass with Time + Memory limits :)

I just don't get why this task has kindof 'small' difficulty, and P11048 has 'large' difficulty.

I'd say this was much more harder than P1148 for me to get AC in Java.