Answers to: NAME2 - Editorialhttps://discuss.codechef.com/questions/9712/name2-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/NAME2">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/NAME2">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES</h1>
<p>Ad-Hoc</p>
<h1>PROBLEM</h1>
<p>Given two strings, say <b>A</b> and <b>B</b>, find whether <b>A</b> is a sub-sequence of <b>B</b>, or whether <b>B</b> is a sub-sequence of <b>A</b>.</p>
<p>A sub-sequence is defined as a string obtained from another string, say <b>S</b>, by <b>deleting</b> <b>one</b> <b>or</b> <b>more</b> characters form <b>S</b>, and not changing the <b>order</b> of the remaining characters.</p>
<h1>QUICK EXPLANATION</h1>
<p>If the length of <b>A</b> is more than the length of <b>B</b>, then <b>A</b> cannot be a sub-sequence of <b>B</b>. This is obvious because you cannot delete characters from B and end up with a string that has <b>more</b> characters than it did orginally.</p>
<p>Thus, if length of <b>A</b> is larger than length of <b>B</b> we can swap them. Now, it only needs to be checked whether <b>A</b> is a sub-sequence of <b>B</b>.</p>
<h1>EXPLANATION</h1>
<p>Checking whether <b>A</b> is a sub-sequence of <b>B</b> can be done greedily.</p>
<p>Let us find the <b>first</b> occurence of the first character of <b>A</b> in <b>B</b>.</p>
<pre>for i = 1 to B.length
if B[i] == A[1]
break
i++
</pre>
<p>If we find that <b>i</b> is larger than <b>B.length</b>, then of course the very first character of <b>A</b> doesn't exist in <b>B</b>. This would mean that it is impossible for <b>A</b> to be a sub-sequence of <b>B</b>.</p>
<p>On the other hand, we have found that the the first character of <b>A</b> occurs in <b>B</b> at position <b>i</b>, first. Now, we can start looking for the <b>second</b> character of <b>A</b>. But, any occurance of the second character of <b>A</b> that occurs before <b>i</b> in <b>B</b> is irrelevant because we cannot perform any operation that <b>changes</b> <b>the</b> <b>order</b> of characters in <b>A</b> (or <b>B</b> for that matter).</p>
<p>Thus, we can resume searching for the second character of <b>A</b> in <b>B</b>, after position <b>i</b>.</p>
<pre>for j = i+1 to B.length
if B[j] == A[2]
break
j++
</pre>
<p>Using the same arguments as above, if <b>j</b> is not more than <b>B.length</b>, we have to resume searching for the third character of <b>A</b> in <b>B</b>, after position <b>j</b>.</p>
<p>When we have found all the characters of <b>A</b> in <b>B</b>, we can safely end the algorithm as well (with a <b>positive</b>). Otherwise we will run out of characters in <b>B</b> and we must return with a <b>negative</b>.</p>
<p>The above algorithm will look like the following pseudo code.</p>
<pre>j = 1
for i = 1 to A.length
while j < B.length
if B[j] == A[i]
break
j++
if j > B.length
return false
i++
j++
return true
</pre>
<p>The complexity of the algorithm is <b>O(|A| + |B|)</b>, where <b>|S|</b> is the length of <b>S</b>. If it is not obvious to you why the algorithm isn't <b>O(|A| * |B|)</b> note that we never decrement the value of <b>j</b>. In every iteration of the above algorithm we always increment <b>i</b> as well as <b>j</b>, and probably increment <b>j</b> more so. Thus, the algorithm must terminate in at most <b>O(|A|)</b> iterations of the outer loop and not more than <b>O(|B|)</b> iterations of the inner loop.</p>
<p>Note how this problem differs from the standard Dynamic Programming problem of finding the <b>largest common sub-sequence</b> between two strings. We could of course solve this problem by finding the longest commong sub-sequence between <b>A</b> and <b>B</b> as well, but doing so requires <b>O(|A| * |B|)</b> which is too slow for the limits set for length of the strings <b>A</b> and <b>B</b>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Setter's solution will be updated soon.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/NAME2.cpp">here</a>.</p>enThu, 27 Apr 2017 20:54:06 +0530Answer by suyash101https://discuss.codechef.com/questions/9712/name2-editorial/96952<p><a href="https://www.codechef.com/viewsolution/13395479">https://www.codechef.com/viewsolution/13395479</a>
what is wrong with the above code ?</p>suyash101Thu, 27 Apr 2017 20:54:06 +0530https://discuss.codechef.com/questions/9712/name2-editorial/96952Answer by sathish11https://discuss.codechef.com/questions/9712/name2-editorial/84456<p>can you verify my code <a href="https://www.codechef.com/viewsolution/11286291">here</a></p>sathish11Wed, 31 Aug 2016 17:43:12 +0530https://discuss.codechef.com/questions/9712/name2-editorial/84456Answer by vickychelseahttps://discuss.codechef.com/questions/9712/name2-editorial/65355<p><a href="http://ideone.com/Y5nHc9">http://ideone.com/Y5nHc9</a></p>
<p>Can anyone help me out with what's wrong in my code ? :)</p>vickychelseaThu, 26 Feb 2015 20:26:11 +0530https://discuss.codechef.com/questions/9712/name2-editorial/65355Answer by gauravhasizahttps://discuss.codechef.com/questions/9712/name2-editorial/64300<p>plzz check my solution</p>gauravhasizaThu, 12 Feb 2015 01:53:16 +0530https://discuss.codechef.com/questions/9712/name2-editorial/64300Answer by ruksharhttps://discuss.codechef.com/questions/9712/name2-editorial/61289<p>Thank you so much :) </p>ruksharMon, 12 Jan 2015 11:11:45 +0530https://discuss.codechef.com/questions/9712/name2-editorial/61289Answer by codester94https://discuss.codechef.com/questions/9712/name2-editorial/60398<p><a href="/users/67644/rukshar">@rukshar</a>
check this out: <a href="http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/">http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/</a></p>codester94Thu, 01 Jan 2015 12:47:58 +0530https://discuss.codechef.com/questions/9712/name2-editorial/60398Answer by ruksharhttps://discuss.codechef.com/questions/9712/name2-editorial/58038<p>Can you provide me a link to learn more about dynamic programming to find largest common sub- sequence between 2 strings.</p>ruksharThu, 11 Dec 2014 17:24:42 +0530https://discuss.codechef.com/questions/9712/name2-editorial/58038Comment by gamabunta on gamabunta's questionhttps://discuss.codechef.com/questions/9712/name2-editorial#9714<p>Sorry the solution links are broken. Will be fixing them shortly!</p>gamabuntaTue, 14 May 2013 15:15:21 +0530https://discuss.codechef.com/questions/9712/name2-editorial#9714