Problem J
Grepping Genes
In researching the global zombie outbreak, you have discovered a way to determine, just by looking at someone’s DNA, whether they have been infected. In particular, there is a certain sequence $Z$ of DNA bases such that someone is infected if and only if their DNA contains $Z$ as a subsequence. (A string $s$ of length $n$ is a subsequence of $t$ if there is an increasing sequence of indices $q_0 < q_1 < \dots < q_{n-1}$ of $t$ such that $s_ i = t_{q_ i}$ for each $0 \leq i < n$.) The only problem is that DNA sequences can be very long! Your only hope of testing DNA fast enough is to write a program to do the testing.
Input
Input consists of two lines. The first line contains the zombie sequence $Z$, and the second line contains the test subject’s DNA $D$. Both $Z$ and $D$ are nonempty strings of length at most $10^5$, consisting solely of the characters A, C, G, and T.
Output
If $Z$ occurs as a subsequence of $D$, output the string “Infected”. Otherwise, output the string “Not infected”.
| Sample Input 1 | Sample Output 1 |
|---|---|
GAC TTTGACTTTT |
Infected |
| Sample Input 2 | Sample Output 2 |
|---|---|
GAC TTTGTTTTTC |
Not infected |
| Sample Input 3 | Sample Output 3 |
|---|---|
GAC TTAGCTTTTT |
Not infected |
