ZOJ Problem Set - 3218
DFA is a special machine, which can be used to found out whether the input string is the one you wanted.
There are a lot of states in the DFA, and some rules are given, which decide where the state needs to be changed to, considering on the input character.
We consider that there are only 3 characters ('a','b','c') in all the strings.
At the beginning, the machine is set to be a start state. In each step, the machine gets in one character from the input string. With the input character, and following the given rules, the machine will change the state to a unique next one.
For example: If the rules given for the state 0 are:
When the input character is 'a': than change the state to state 0; When the input character is 'b': than change the state to state 2; When the input character is 'c': than change the state to state 1;
So if the machine is on state 0 now, considering the input character 'a', 'b' or 'c', it will change the state to 0, 2 or state 1. Then it will continue this kind of work, until all the input string had been dealt with totally.
When all the characters have been work out, there is a final state come out. If the final state belongs to the accepted set, we can say that, this input string is one of you wanted. Or, the string is not.
The rules for one state can be written as:
i j k l Y/N (there is a blank between i,j,k,l,Y/N, which is important for you to output.)
i is the current state.(count from 0, that means if there are total t states, must be 0,1,2...t-1)
j, k or l is the next state when input is 'a', 'b' or 'c'.
Y/N shows that if this state is in the accepted set. 1 means yes, while 0 means no.
At the beginning, the machine must begin at state 0.
For example, this is a table of the DFA (also same to the output you need to print, so be careful.)
0 0 2 1 1
1 1 2 1 1
2 2 2 2 0
The first 3 means that: there are 3 states in this machine. So there are 3 lines followed.
If the input string is "abc", then the state will change as: 0->0->2->2. The final state is 2, but 2 is not in accepted set, so the string "abc" is not you wanted.
While if the input string is "caa", the final state is 1, in the accepted set. So "caa" is one of you wanted.
There are many input case. The first line of the input is an integer T (T <= 150), indicating the number of cases.
Each case begin with an integer n (0 < n < 6) then n+1 lines followed. Each line is a string containing only 'a','b' or 'c'. The n+1 strings are different from each other.
The first n line are the strings you must accepted, while the last one can not be accepted.
Each string is less than 100 characters and is not empty.
For each case, print one DFA machine satisfied with the input case. Also, you can use no more than 200 states in your machine. If there is more than one answer, any one is ok. Print a blank line after each case.
2 1 caa abc 5 abcabc abcabcabc abcabcabcabc abcabcabcabcabc abcabcabcabcabcabc abc
3 0 0 2 1 1 1 1 2 1 1 2 2 2 2 0 9 0 1 0 0 0 1 0 2 0 0 2 0 0 3 0 3 4 0 0 0 4 0 5 0 0 5 0 0 6 0 6 7 0 0 1 7 0 8 0 0 8 0 0 6 0
Author: YU, Zhi
Source: ZOJ Monthly, June 2009