Конечные автоматы!

[videolord]

Как можно написать с помошью конечных автоматов (Было бы классно если можно написать с помошью Детерминированных и недетерминированных конечных автоматов )

Дано массив слов String[] dir={"out","output","puton","in","i nput","one"};
если введенная строка состоит из этих слов то вывести "yes"
если нет то No

Ввод
oneputonininputoutoutput
Вывод
Yes

Ввод
inonputin
Вывод
No

Ввот ссылка на задачу http://acm.timus.ru/problem.aspx?space=1&num=1102
Написал с помошью регулярных выражений но хавает очень много памяти
Memory limit exceeded on test 1 Выделено памяти 16 630 КБ,а ограничение 16мб!

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class regex {
public static void main(String[] args)  throws IOException {
Scanner sc=new Scanner(System.in);
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n=sc.nextInt();
String str;
Pattern p =Pattern.compile("^(out(put)?|puton|in(put)?|one)+$");
for(int i=0;i<n;i++){
Matcher m = p.matcher(reader.readLine());
if (m.matches()==true)
System.out.println("YES");	
else
System.out.println("NO");
}}
}