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

I would recommend using gets() for all that want to have the whole string at once. It still is fast enough and does not time limit.

How exactly do you use DFS for this?  Can you provide an example of some other problem similar to this which is solvable by DFS?  Thank you.

It's Not DFS problem!!!!! It's DFA(Deterministic finite automaton) problem!

I solved it with DFS in 0.453 sec.

When I was using STL, I always had TL on the first test but I was sure that this is the correct algo. Then I replaced all STL's strings with array of chars and I got ACC 0.078 . OMGWTF ?!

First test is really large.  Something of order 1e6.

Its a simple substring search problem.