Co-occurrence Search

A huge amount of information is being heaped on WWW. Albeit it is not well-organized, users can browse WWW as an unbounded source of up-to-date information, instead of consulting established but a little out-of-date encyclopedia. However, you can further exploit WWW by learning more about keyword search algorithms.

For example, if you want to get information on recent comparison between Windows and UNIX, you may expect to get relevant description out of a big bunch of Web texts, by extracting texts that contain both keywords "Windows" and "UNIX" close together.

Here we have a simplified version of this co-occurrence keyword search problem, where the text and keywords are replaced by a string and key characters, respectively. A character string S of length n (1 ≤ n ≤ 1, 000, 000) and a set K of k distinct key characters a1, ..., ak (1 ≤ k ≤ 50) are given. Find every shortest substring of S that contains all of the key characters a1, ..., ak.

The input is a text file which contains only printable characters (ASCII codes 21 to 7E in hexadecimal) and newlines. No white space such as space or tab appears in the input.

The text is a sequence of the shortest string search problems described above. Each problem consists of character string Si and key character set Ki (i = 1, 2, ..., p). Every Si and Ki is followed by an empty line. However, any single newline between successive lines in a string should be ignored; that is, newlines are not part of the string. For various technical reasons, every line consists of at most 72 characters. Each key character set is given in a single line. The input is terminated by consecutive empty lines; p is not given explicitly.

All of p problems should be solved and their answers should be output in order. However, it is not requested to print all of the shortest substrings if more than one substring is found in a problem, since found substrings may be too much to check them all. Only the number of the substrings together with their representative is requested instead. That is, for each problem i, the number of the shortest substrings should be output followed by the first (or the leftmost) shortest substring si1, obeying the following format:

the number of the shortest substrings for the i-th problem
empty line
the first line of si1
the second line of si1
...
the last line of si1
empty line for the substring termination

where each line of the shortest substring si1 except for the last line should consist of exactly 72 characters and the last line (or the single line if the substring is shorter than or equal to 72 characters, of course) should not exceed 72 characters.

If there is no such substring for a problem, the output will be a 0 followed by an empty line; no more successive empty line should be output because there is no substring to be terminated.