Number of Ways to Transform a String into a Substring

Given two sequences A and B, find out number of unique ways to transform sequence A into sequence B. Transformation means converting string A (by removing 0 or more characters) to string B.

Examples:

When inputs are A = "abcccdf" and B = "abccdf", the output should be 3. Three ways to transform A into B are "ab.ccdf", "abc.cdf" and "abcc.df".

When inputs are A = "aabba" and B = "ab", the output should be 4. Four ways to transform A into B are "a.b..", "a..b.", ".ab.." and ".a.b.".

Contributed by Berkan Teber