Let x be a string of length n, and let y be a string of length n k, for

1 k < n.

We wish to line up the symbols in x with the symbols in y by adding k blanks to y. How many ways are there to do this? Design a recursive algorithm for traversing all the ways to add blanks to the smaller string. Investigate the complexity of your algorithm.