Internet Problem Solving Contest

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”.