1) Start with the FOUR final states.
2) Use only 15 states.
3) If it doesn't work out, then read the hint further.
unsigned char constexpr stopStates = 4;
auto constexpr go = []() {//state machine (2D array)
    std::array<std::array<decltype(+stopStates),256>,15> g;
    for(auto&e : g)    //default
        std::fill(e.begin(), e.end(), g.size());//wrong state
    for(size_t i = 0; i!=stopStates; ++i)    //default
        g[i]['i'] = stopStates, g[i]['o'] = stopStates+1;
    //===== stop states =====
    g[0]['p'] = 8;   //puton
    //in \ out
    g[1]['p'] = 12;  //put
    //input \ output
    g[2]['o'] = 14;  //on
    g[2]['p'] = 8;   //puton
    //put_on
    g[3]['p'] = 8;   //puton
    g[3]['e'] = 0;   //e
    //===== non stop states =====
    g[4]['n'] = 1;   // i -> in
    g[5]['n'] = 6;   // o -> on
    g[5]['u'] = 7;   // o -> ou
    g[6]['e'] = 0;   // on -> one
    g[7]['t'] = 1;   // ou -> out
    g[8]['u'] = 9;   // p -> pu
    g[9]['t'] = 10;  // pu -> put
    g[10]['o'] = 11; // put -> puto
    g[11]['n'] = 0;  // puto -> puton
    g[12]['u'] = 13; // ?p -> ?pu
    g[13]['t'] = 2;  // ?pu -> ?put
    g[14]['n'] = 3;  // ?puto -> ?puton
    g[14]['u'] = 7;  // ?puto -> ?putou
    return g;
    //todo: Timus - automatic construction of a MINIMAL state machine (NP ?)
}();

The total length of all strings (including the first one with the number N) exceeds the specified size of 4000000 bytes.

New tests were added. 192 authors lost AC.

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