prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem H:</font> Co-occurrence Search</H1>3 4<p>5A 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.6</p>7<p>8For 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.9</p>10<p>11Here 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 <i>n</i> (1 &le; <i>n</i> &le; 1,000,000) and a set <i>K</i> of <i>k</i> distinct key characters <i>a</i><sub>1</sub>, ..., <i>a<sub>k</sub></i> (1 &le; <i>k</i> &le; 50) are given. Find every shortest substring of <i>S</i> that contains all of the key characters <i>a</i><sub>1</sub>, ..., <i>a<sub>k</sub></i>. 12</p>13 14<H2>Input</H2>15 16<p>17The 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.18</p>19<p>20The text is a sequence of the shortest string search problems described above. Each problem consists of character string <i>S<sub>i</sub></i> and key character set <i>K<sub>i</sub></i> (<i>i</i> = 1, 2, ..., <i>p</i>). Every <i>S<sub>i</sub></i> and <i>K<sub>i</sub></i> 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; <i>p</i> is not given explicitly. 21</p>22 23<H2>Output</H2>24 25<p>26All of <i>p</i> 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>i</i>, the number of the shortest substrings should be output followed by the first (or the leftmost) shortest substring <i>s</i><sub><i>i</i>1</sub>, obeying the following format:27</p>28 29<pre>30<i>31    the number of the shortest substrings for the i-th problem32    empty line33    the first line of s<sub>i1</sub>34    the second line of s<sub>i1</sub>35    ...36    the last line of s<sub>i1</sub>37    empty line for the substring termination 38</i>39</pre>40<p>41where each line of the shortest substring <i>s</i><sub><i>i</i>1</sub> 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.42</p>43<p>44If 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. 45</p>46 47<H2>Sample Input</H2>48<pre>49Thefirstexampleistrivial.50 51mfv52 53AhugeamountofinformationisbeingheapedonWWW.Albeititisnot54well-organized,userscanbrowseWWWasanunboundedsourceof55up-to-dateinformation,insteadofconsultingestablishedbutalittle56out-of-dateencyclopedia.However,youcanfurtherexploitWWWby57learningmoreaboutkeywordsearchalgorithms.Forexample,ifyou58wanttogetinformationonrecentcomparisonbetweenWindowsandUNIX,59youmayexpecttogetrelevantdescriptionoutofabigbunchofWeb60texts,byextractingtextsthatcontainbothkeywords"Windows"and"UNIX"61closetogether.62 63bWn64 653.141592653589793238462643383279502884197169399375105820974944592307816466 67pi68 69Wagner,Bach,Beethoven,Chopin,Brahms,Hindemith,Ives,Suk,Mozart,Stravinsky70 71Weary72 73ASCIIcharacterssuchas+,*,[,#,<,},_arenotexcludedinagivenstringas74thisexampleillustratesbyitself.Youshouldnotforgetthem.Onemorefact75youshouldnoticeisthatuppercaselettersandlowercaselettersare76distinguishedinthisproblem.Don'tidentify"g"and"G",forexmaple.77However,weareafraidthatthisexamplegivesyoutoomuchhint!78 79![GsC_l80 81ETAONRISHDLFCMUGYPWBVKXJQZ82 83ABCDEFGHIJKLMNOPQRSTUVWXYZ84 85 86</pre>87 88<H2>Output for the Sample Input</H2>89<pre>90191 92firstexampleistriv93 94795 96nWWW.Alb97 98099 1001101 102Wagner,Bach,Beethoven,Chopin,Brahms,Hindemith,Ives,Suk,Mozart,Stravinsky103 1041105 106CIIcharacterssuchas+,*,[,#,<,},_arenotexcludedinagivenstringasthisexampl107eillustratesbyitself.Youshouldnotforgetthem.Onemorefactyoushouldnoticeis108thatuppercaselettersandlowercaselettersaredistinguishedinthisproblem.Don109'tidentify"g"and"G",forexmaple.However,weareafraidthatthisexamplegivesyo110utoomuchhint!111 1121113 114ETAONRISHDLFCMUGYPWBVKXJQZ115 116</pre>117 118