prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8 9<h2>Problem D10Hidden Anagrams11</h2>12 13<p>14An <i>anagram</i> is a word or a phrase that is formed by rearranging the letters of another. For instance, by rearranging the letters of "William Shakespeare," we can have its anagrams "I am a weakish speller," "I'll make a wise phrase," and so on. Note that when $A$ is an anagram of $B$, $B$ is an anagram of $A$.15</p>16 17<p>18In the above examples, differences in letter cases are ignored, and word spaces and punctuation symbols are freely inserted and/or removed. These rules are common but not applied here; only exact matching of the letters is considered.19</p>20 21<p>22For two strings $s_1$ and $s_2$ of letters, if a substring $s'_1$ of $s_1$ is an anagram of a substring $s'_2$ of $s_2$, we call $s'_1$ a <i>hidden anagram</i> of the two strings, $s_1$ and $s_2$. Of course, $s'_2$ is also a <i>hidden anagram</i> of them.23</p>24 25<p>26Your task is to write a program that, for given two strings, computes the length of the longest hidden anagrams of them.27</p>28 29<p>30Suppose, for instance, that "anagram" and "grandmother" are given. Their substrings "nagr" and "gran" are hidden anagrams since by moving letters you can have one from the other. They are the longest since any substrings of "grandmother" of lengths five or more must contain "d" or "o" that "anagram" does not. In this case, therefore, the length of the longest hidden anagrams is four. Note that a substring must be a sequence of letters occurring <i>consecutively</i> in the original string and so "nagrm" and "granm" are not hidden anagrams.31</p>32 33 34<h3>Input</h3>35 36<p>37The input consists of a single test case in two lines.<br/>38<br/>39$s_1$<br/>40$s_2$<br/>41</p>42 43<p>44$s_1$ and $s_2$ are strings consisting of lowercase letters (a through z) and their lengths are between 1 and 4000, inclusive.45</p>46 47 48<h3>Output</h3>49 50<p>51Output the length of the longest hidden anagrams of $s_1$ and $s_2$. If there are no hidden anagrams, print a zero.52</p>53 54 55<h3>Sample Input 1</h3>56 57<pre>anagram58grandmother</pre>59 60<h3>Sample Output 1</h3>61 62<pre>4</pre>63 64<br/>65 66<h3>Sample Input 2</h3>67 68<pre>williamshakespeare69iamaweakishspeller</pre>70 71<h3>Sample Output 2</h3>72 73<pre>18</pre>74 75<br/>76 77<h3>Sample Input 3</h3>78 79<pre>aaaaaaaabbbbbbbb80xxxxxabababxxxxxabab</pre>81 82<h3>Sample Output 3</h3>83 84<pre>6</pre>85 86<br/>87 88<h3>Sample Input 4</h3>89 90<pre>abababacdcdcd91efefefghghghghgh</pre>92 93<h3>Sample Output 4</h3>94 95<pre>0</pre>96 97 98 99