## IPSC 2016

## Solution to Problem S – Subsequence

The easy subproblem can be solved by almost any reasonable algorithm. For example, we can try all possible triples of indices into *A* and check whether those letters form *B*. This can easily be done using three nested cycles.

To solve the hard subproblem, we can use a greedy algorithm that runs in linear time. We go through all of letters from *B* and for each letter we find the first possible match in *A* after the match of the previous letter.

For example, when checking whether “DOG” is a subsequence of some string *A*, you can look for the first “D”, then the first “O” after that “D”, and then the first “G” after that “O”.