1420. Zipper

In this program, we will determine if it is possible to produce a target string by interleaving the characters of two source strings. While this is reminiscent of how two sides of a zipper come together when zipped, we won't require one-by-one alternation and will allow any number of successive characters of one source string to come between two successive characters of the other source string.

Input Format

Each line of input will contain three nonempty strings of non-blank graphical ASCII characters separated by single blank characters. Length of any string is not more 100 characters. The first two strings are known as the left source string `l` and the right source string `r`, and the third string is known as the target string `c`.

Output Format

For each line of input, determine whether or not the target string `c` contains a subsequence that matches the left source string `l`, and by removing the characters of `l` from `c` leaves the right source string `r`. Answer yes or no followed by the source strings and target string formatted as shown in the output sample.

abcd efgh abefcgdh
what up whatup
what up upwhat
yerps cbace cyberspace
yerpc cbsae cyberspace
these are crazy
000000 000000 00000000000

yes: abcd ~ efgh =? abefcgdh
yes: what ~ up =? whatup
yes: what ~ up =? upwhat
 no: yerps ~ cbace =? cyberspace
yes: yerpc ~ cbsae =? cyberspace
 no: these ~ are =? crazy
 no: 000000 ~ 000000 =? 00000000000