Problem Statement:
You are given 2 strings, you need to find how many times string 2 appears as subsequence in string 1.
Example
string = “subsequence”
pattern = “ue”
Output: 4
subsequence
- -
subsequence
- -
subsequence
- -
subsequence
--
subsequence
- -Solution
The solution is similar to LCS problem
Here we need to check how many times the pattern appears in string 1.
We start from the last character of both of the strings.
If the last character matches, there are 2 possible choices:
1. We accept the matching and then decrement both the strings and then check for next characters.
2. As we need to find all the occurance of the substring, we can ignore the match and decrement only string 1. And check if there are any other matches.
If the last character does not matches, then just decrement the string 1.
Solution in C++
#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <unordered_map>
#include <list>
using namespace std;
int recursion(string a, string b, int m, int n)
{
// base case if substring is present
// If both of the string are empty or if pattern string is empty
// then it is a match and return 1.
if ((m == 0 && n == 0) || n == 0)
return 1;
// if only first string is empty, then there is no match
if (m == 0)
return 0;
// if the last characters match, then
// we have 2 choices.
if (a[m - 1] == b[n - 1])
return recursion(a, b, m - 1, n - 1) +
recursion(a, b, m - 1, n);
else
// if the last char did not match, then
// decrement the first string.
return recursion(a, b, m - 1, n);
}
int bottom_up_approach(string a, string b)
{
int m = a.length();
int n = b.length();
// create a table to store the values of sub problems
int table[m + 1][n + 1] ;
for (int i = 0; i <= n; ++i)
table[0][i] = 0;
for (int i = 0; i <= m; ++i)
table[i][0] = 1;
// fill the table in bottom up manner.
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// if last char are same, then we have 2 choices
if (a[i - 1] == b[j - 1])
table[i][j] = table[i - 1][j - 1] +
table[i - 1][j];
else
// if they did not match.
table[i][j] = table[i - 1][j];
}
}
return table[m][n];
}
int main()
{
string String = "subsequence";
string pattern = "ue";
cout<<"The pattern is repeating using recursion is = "<<recursion(String, pattern, String.size(), pattern.size())<<" times"<<endl;
cout<<"The pattern is repeating using bottom up approach is = "<<bottom_up_approach(String, pattern)<<" times"<<endl;
}Output:
The pattern is repeating using recursion is = 5 times
The pattern is repeating using bottom up approach is = 5 times