You are not logged in. Please login at www.codechef.com to post your questions!

×

NAME2 - Editorial

2
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad-Hoc

PROBLEM

Given two strings, say A and B, find whether A is a sub-sequence of B, or whether B is a sub-sequence of A.

A sub-sequence is defined as a string obtained from another string, say S, by deleting one or more characters form S, and not changing the order of the remaining characters.

QUICK EXPLANATION

If the length of A is more than the length of B, then A cannot be a sub-sequence of B. This is obvious because you cannot delete characters from B and end up with a string that has more characters than it did orginally.

Thus, if length of A is larger than length of B we can swap them. Now, it only needs to be checked whether A is a sub-sequence of B.

EXPLANATION

Checking whether A is a sub-sequence of B can be done greedily.

Let us find the first occurence of the first character of A in B.

for i = 1 to B.length
    if B[i] == A[1]
        break
    i++

If we find that i is larger than B.length, then of course the very first character of A doesn't exist in B. This would mean that it is impossible for A to be a sub-sequence of B.

On the other hand, we have found that the the first character of A occurs in B at position i, first. Now, we can start looking for the second character of A. But, any occurance of the second character of A that occurs before i in B is irrelevant because we cannot perform any operation that changes the order of characters in A (or B for that matter).

Thus, we can resume searching for the second character of A in B, after position i.

for j = i+1 to B.length
    if B[j] == A[2]
        break
    j++

Using the same arguments as above, if j is not more than B.length, we have to resume searching for the third character of A in B, after position j.

When we have found all the characters of A in B, we can safely end the algorithm as well (with a positive). Otherwise we will run out of characters in B and we must return with a negative.

The above algorithm will look like the following pseudo code.

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

The complexity of the algorithm is O(|A| + |B|), where |S| is the length of S. If it is not obvious to you why the algorithm isn't O(|A| * |B|) note that we never decrement the value of j. In every iteration of the above algorithm we always increment i as well as j, and probably increment j more so. Thus, the algorithm must terminate in at most O(|A|) iterations of the outer loop and not more than O(|B|) iterations of the inner loop.

Note how this problem differs from the standard Dynamic Programming problem of finding the largest common sub-sequence between two strings. We could of course solve this problem by finding the longest commong sub-sequence between A and B as well, but doing so requires O(|A| * |B|) which is too slow for the limits set for length of the strings A and B.

SETTER'S SOLUTION

Setter's solution will be updated soon.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 14 May '13, 15:14

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 16 May '13, 12:46

admin's gravatar image

0★admin ♦♦
19.8k350498541

Sorry the solution links are broken. Will be fixing them shortly!

(14 May '13, 15:15) gamabunta1★

Can you provide me a link to learn more about dynamic programming to find largest common sub- sequence between 2 strings.

link

answered 11 Dec '14, 17:24

rukshar's gravatar image

0★rukshar
1
accept rate: 0%

link

answered 01 Jan '15, 12:47

codester94's gravatar image

4★codester94
11
accept rate: 0%

Thank you so much :)

link

answered 12 Jan '15, 11:11

rukshar's gravatar image

0★rukshar
1
accept rate: 0%

plzz check my solution

link

answered 12 Feb '15, 01:53

gauravhasiza's gravatar image

3★gauravhasiza
1
accept rate: 0%

http://ideone.com/Y5nHc9

Can anyone help me out with what's wrong in my code ? :)

link

answered 26 Feb '15, 20:26

vickychelsea's gravatar image

2★vickychelsea
1
accept rate: 0%

can you verify my code here

link

answered 31 Aug '16, 17:43

sathish11's gravatar image

2★sathish11
1
accept rate: 0%

https://www.codechef.com/viewsolution/13395479 what is wrong with the above code ?

link

answered 27 Apr '17, 20:54

suyash101's gravatar image

0★suyash101
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,683
×1,652
×951
×18

question asked: 14 May '13, 15:14

question was seen: 5,411 times

last updated: 01 Feb '18, 09:20