Find number of times a string occurs as a subsequence
Given two strings S and T, find the number of times the second string occurs in the first string, whether continuous or discontinuous as subsequence.
Input: String S: "iloveincludehelp" String T: "il" Output: 5
The first string is,
The second string is "il"
So, total distinct occurrences are 5.
First, we discuss the recursive solution and then we will convert it to dynamic programming.
How, how can we generate a recursive relation?
Now we have to option,
Now we have only one option which is check for starts+1, startt as we need to look for different occurrence only.
The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming. (I would recommend to take two short string and try doing by your hand and draw the recursion tree to understand how recursion is working).
Let's convert the recursion to DP.