prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem B: </font>The Sorcerer's Donut </H1>3 4<p>5Your master went to the town for a day. You could have a relaxed day without hearing his6scolding. But he ordered you to make donuts dough by the evening. Loving donuts so much, he7can't live without eating tens of donuts everyday. What a chore for such a beautiful day.8</p>9 10<p>11But last week, you overheard a magic spell that your master was using. It was the time to12try. You casted the spell on a broomstick sitting on a corner of the kitchen. With a flash of13lights, the broom sprouted two arms and two legs, and became alive. You ordered him, then he14brought flour from the storage, and started kneading dough. The spell worked, and how fast he15kneaded it!16</p>17 18<p>19A few minutes later, there was a tall pile of dough on the kitchen table. That was enough for20the next week. \OK, stop now." You ordered. But he didn't stop. Help! You didn't know the21spell to stop him! Soon the kitchen table was filled with hundreds of pieces of dough, and he22still worked as fast as he could. If you could not stop him now, you would be choked in the23kitchen filled with pieces of dough.24</p>25 26<p>27Wait, didn't your master write his spells on his notebooks? You went to his den, and found the28notebook that recorded the spell of cessation.29</p>30 31<p>32But it was not the end of the story. The spell written in the notebook is not easily read by33others. He used a plastic model of a donut as a notebook for recording the spell. He split the34surface of the donut-shaped model into square mesh (Figure B.1), and filled with the letters35(Figure B.2). He hid the spell so carefully that the pattern on the surface looked meaningless.36But you knew that he wrote the pattern so that the spell "appears" more than once (see the next37paragraph for the precise conditions). The spell was not necessarily written in the left-to-right38direction, but any of the 8 directions, namely left-to-right, right-to-left, top-down, bottom-up,39and the 4 diagonal directions.40</p>41 42<p>43You should be able to find the spell as the longest string that appears more than once. Here,44a string is considered to appear more than once if there are square sequences having the string45on the donut that satisfy the following conditions.<br><br>46<li>Each square sequence does not overlap itself. (Two square sequences can share some squares.)</li>47<li>The square sequences start from different squares, and/or go to different directions.</li>48 49</p>50	51<center>52<table width="480">53<tr>54<td>55<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1316_1">56</td>57<td>58<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1316_2">59</td>60<tr>61<td>62<b>Figure B.1: The Sorcerer's Donut Before63Filled with Letters, Showing the Mesh and 864Possible Spell Directions </b>65</td>66<td valign="top">67<b>68Figure B.2: The Sorcerer's Donut After Filled69with Letters70</b>71</td>72</tr>73</table>74</center>75 76<p>77Note that a palindrome (i.e., a string that is the same whether you read it backwards or forwards)78that satisfies the first condition "appears" twice.79</p>80 81<p>82The pattern on the donut is given as a matrix of letters as follows.83</p>84<pre>85ABCD86EFGH87IJKL88</pre>89 90<p>91Note that the surface of the donut has no ends; the top and bottom sides, and the left and right92sides of the pattern are respectively connected. There can be square sequences longer than both93the vertical and horizontal lengths of the pattern. For example, from the letter F in the above94pattern, the strings in the longest non-self-overlapping sequences towards the 8 directions are95as follows.96</p>97 98<pre>99FGHE100FKDEJCHIBGLA101FJB102FIDGJAHKBELC103FEHG104FALGBIHCJEDK105FBJ106FCLEBKHAJGDI107</pre>108 109<p>110Please write a program that finds the magic spell before you will be choked with pieces of donuts111dough.112</p>113 114<H2>Input</H2>115 116<p>117The input is a sequence of datasets. Each dataset begins with a line of two integers <i>h</i> and <i>w</i>,118which denote the size of the pattern, followed by <i>h</i> lines of <i>w</i> uppercase letters from A to Z,119inclusive, which denote the pattern on the donut. You may assume 3 &le; <i>h</i> &le; 10 and 3 &le; <i>w</i> &le; 20.120</p>121 122<p>123The end of the input is indicated by a line containing two zeros.124</p>125 126 127<H2>Output</H2>128 129<p>130For each dataset, output the magic spell. If there is more than one longest string of the same131length, the first one in the dictionary order must be the spell. The spell is known to be at least132two letters long. When no spell is found, output 0 (zero).133</p>134 135<H2>Sample Input</H2>136<pre>1375 7138RRCABXT139AABMFAB140RROMJAC141APTADAB142YABADAO1433 13144ABCDEFGHIJKLM145XMADAMIMADAMY146ACEGIKMOQSUWY1473 4148DEFG149ACAB150HIJK1513 6152ABCDEF153GHIAKL154MNOPQR15510 19156JFZODYDXMZZPEYTRNCW157XVGHPOKEYNZTQFZJKOD158EYEHHQKHFZOVNRGOOLP159QFZOIHRQMGHPNISHXOC160DRGILJHSQEHHQLYTILL161NCSHQMKHTZZIHRPAUJA162NCCTINCLAUTFJHSZBVK163LPBAUJIUMBVQYKHTZCW164XMYHBVKUGNCWTLLAUID165EYNDCCWLEOODXYUMBVN1660 0167</pre>168 169<H2>Output for the Sample Input</H2>170<pre>171ABRACADABRA172MADAMIMADAM173ABAC1740175ABCDEFGHIJKLMNOPQRSTUVWXYZHHHHHABCDEFGHIJKLMNOPQRSTUVWXYZ176</pre>