Figure 1. An example of NFA A with 13 states, over alphabet {a, b, c}. The lexicographically smallest word among all shortest words, which are accepted by A and which contain the string ab as a substring, is the word W = acabc. The sequence of transitions leading to W being accepted by A is highlighted. The image illustrates Example 1 below. |
There is a non-deterministic finite automaton (NFA) A over a short alphabet Σ. There is also an unempty string S over the same alphabet. The task is to find the lexicographically smallest word among all shortest words which are accepted by A and which contain S as a substring.
The first line contains two positive integers N, M separated by space and representing (in this order)
the number of states in NFA A and the size of the alphabet Σ.
The states of A are labeled 0, 1, ..., N−1.
Next, there are N lines specifying the transition table of A. Each line represents one state.
A line starts with the label of the state and a mark which says whether the state is final or not.
The mark is either '−' (minus sign) or 'F', final states are marked by 'F', all other states are marked by '−' (minus sign).
Next, the line contains all characters of Σ listed in ascending order.
Each character is followed by a list of states
to which A may transit from the current state after reading the corresponding character.
The list is not sorted and may be empty.
All values on a line are separated by one or more spaces,
a line may also contain one or more leading spaces (for better visual perception).
The states of A are listed in ascending order of their labels,
the state labeled 0 is the start state of A.
The last line of input contains an unempty word S over Σ.
The size M of alphabet Σ is at most 5 and Σ consists of M consecutive
lower characters of English alphabet, always starting from 'a'.
The value of N does not not exceed 2000, the length of S is at most 10.
The number of transitions in A does not exceed 20000.
The output consists of one line containing one string representing the lexicographically smallest word
among all shortest words which are accepted by A and which contain S as a substring.
The existence of solution is guaranteed for each automaton in the problem data sets.
Note that a word may be its own substring.
13 3 0 - a 1 b 3 c 1 - a 2 5 b c 4 2 F a b c 3 - a b c 4 4 - a 5 7 b c 5 - a 8 b 6 c 6 - a b c 9 7 - a 8 b 10 c 8 F a b 9 c 9 - a 11 b c 10 - a b 12 c 11 11 - a b 3 c 12 F a b c abOutput
acabb
18 4 0 F a 1 2 3 b c d 1 F a 4 b 4 c d 2 F a 4 b c 4 d 3 F a 4 b c d 4 4 F a 5 6 7 b c d 5 - a 8 b 8 c d 6 - a 8 b c 8 d 7 - a 8 b c d 8 8 - a 9 10 11 b c d 9 - a 12 b 12 c d 10 - a 12 b c 12 d 11 - a 12 b c d 12 12 - a 13 14 15 b c d 13 - a 16 b 16 c d 14 - a 16 b c 16 d 15 - a 16 b c d 16 16 - a 17 b c d 17 17 F a b c d abaOutput
aaaaaaaba
6 5 0 - a b c d 1 e 1 F a b 4 c d e 2 2 - a b c d e 3 3 - a 4 b c d e 4 - a b 5 c d e 5 - a b c 0 d e abcdeOutput
deeabcdeeabcd
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set