Spoj (SUBS) – String it out

http://www.spoj.com/problems/SUBS/

There is  a very interesting algorithmic approach for this problem

(Thanks to topcoder forum from where i got this idea)

To find the maximum power using which X can be expanded such that X is a subsequence in Y

highest possible power = length_of_Y/length_of_X

lowest power= 0

Now using binary search find the maximum valid power whose value is in the range [0,highest possible power]

[gist https://gist.github.com/vishnujayvel/7907760 ]