# NAME2 - Editorial

#PROBLEM LINKS
[Practice][1]
[Contest][2]
#DIFFICULTY
CAKEWALK
#PREREQUISITES
Ad-Hoc
#PROBLEM
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>.
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.
#QUICK EXPLANATION
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.
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>.
#EXPLANATION
Checking whether <b>A</b> is a sub-sequence of <b>B</b> can be done greedily.
Let us find the <b>first</b> occurence of the first character of <b>A</b> in <b>B</b>.
<pre>
for i = 1 to B.length
if B[i] == A[1]
break
i++
</pre>
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>.
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).
Thus, we can resume searching for the second character of <b>A</b> in <b>B</b>, after position <b>i</b>.
<pre>
for j = i+1 to B.length
if B[j] == A[2]
break
j++
</pre>
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>.
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>.
The above algorithm will look like the following pseudo code.
<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>
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.
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>.
#SETTER'S SOLUTION
~~Can ~~Setter's solution will be ~~found [here][3].
~~updated soon.
#TESTER'S SOLUTION
Can be found [here][4].
[1]: http://www.codechef.com/problems/NAME2
[2]: http://www.codechef.com/MAY13/problems/NAME2
[3]: http://www.codechef.com/download/Solutions/2013/May/Setter/NAME2.cpp
[4]: http://www.codechef.com/download/Solutions/2013/May/Tester/NAME2.cpp