You are given several dictionaries, each of them consisting of nonempty words over the alphabet 'a',..,'z', and a text over the same alphabet. Your task is to find the shortest substring (a continuous subsequence of characters) of the text which contains (as its substrings) at least one word from each dictionary. If there are more feasible substrings of the minimal length, we search for that one with the smallest start index.
The first line of the input contains a text to be processed.
The second line contains an integer D which is the number of dictionaries. The remaining lines represent dictionaries.
Representation of a dictionary starts by a line containing integer N which gives the number of words in the dictionary. The words are written in the next
N lines, one word per line, in an arbitrary order.
A word can be contained in several dictionaries. Each dictionary contains at least one word and all its words are distinct. The text length is not greater than 3 × 106, the number of dictionaries does not exceed 2000, the sum of dictionaries sizes (where dictionary size is the number of words in the dictionary) does not exceed 8000. Each word has at most 20 characters. It is guaranteed that the input text contains at least one word from each dictionary as its substring.
Let the searched optimal substring be of length L, starting at position P (note that the first character of the text is at position 0). The output consists of two lines where the first line contains P and the second line contains L.
jelenovipivonelej 2 3 jelen jel pivo 3 lej jen pitoOutput
8 9The searched substring is the suffix 'pivonelej', containing 'pivo' from the first dictionary and 'lej' from the second dictionary.
kralsekalakapralkafral 3 3 kral lak sekat 3 pral a kral 2 prak kalOutput
6 5The searched substring is 'kalak', starting at position 6. It contains 'lak', 'a' and 'kal', which are words from all three dictionaries.
kolkolemdokolenolemokolopolendopoleprolen 4 4 koleno poleno soleno pro 3 len lem dok 2 role kolem 5 kolem len polen mok proOutput
35 6The searched substring is the suffix 'prolen'.
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