Hidden Password

Say that, if the characters of X appear in Y in the same order that they appear in X, then X is hidden in Y. So, if X is “ABC” and Y is “HAPPYBIRTHDAYCACEY”, then X is hidden in Y. However, if X is “ABC” and Y is “TRAGICBIRTHDAYCACEY”, then X is not hidden in Y, because “C” appears before “B” in “TRAGICBIRTHDAYCACEY”. Of course, if X is “ABC” and Y is “HAPPYBIRTHDAY”, then X is not hidden in Y, because “C” never appears in “HAPPYBIRTHDAY”.

Now, given two strings X and Y, decide whether X is hidden in Y.

In the ACM-ICPC’s 2015 Mid-Central USA Programming Contest, this problem appeared in the guise of deciding whether a given password is hidden inside a given message. My solution to the problem is recursive:

1) If X is empty, then it is vacuously true that X is hidden in Y.

2) If X is nonempty and Y is empty, then it is false that X is hidden in Y.

3) If the first character of X and the first character of Y are the same, then continue the procedure on the rest of X and the rest of Y.

4) If the first character of X and the first character of Y are different, but the first character of Y appears somewhere else in X, then it is false that X is hidden in Y.

5) If none of the above conditions obtains, then continue the procedure on X and the rest of Y.

My Python code and my Scheme code are both up at my GitHub.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s