Problem 68: Distinct Subsequences
Problem Statement: Given two strings s and t, count the number of distinct subsequences of s which equals t. Print the result modulo 10^9+7.
Input
The first line contains s and the second line contains t.
Output
Print the number of distinct subsequences of s that equal t modulo 10^9+7.
Examples
Input:
rabbbit
rabbit
Output:
3
Solution Explanation
Use dynamic programming where dp[i][j] denotes the number of ways t[0..j-1] appears as a subsequence in s[0..i-1]. Transition based on matching characters.
Solution in C++
#include
#include
#include
using namespace std;
const int MOD = 1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector> dp(n + 1, vector(m + 1, 0));
for(int i = 0; i <= n; i++)
dp[i][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i - 1][j];
if(s[i - 1] == t[j - 1])
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
}
}
cout << dp[n][m] << "\n";
return 0;
}