Count distinct occurrences as a subsequence | C / C ++ program to count number of times S appears as a subsequence in T ; T can 't appear as a subsequence in S ; mat [ i ] [ j ] stores the count of occurrences of T ( 1. . i ) in S ( 1. . j ) . ; Initializing first column with all 0 s . An empty string can 't have another string as suhsequence ; Initializing first row with all 1 s . An empty string is subsequence of all . ; Fill mat [ ] [ ] in bottom up manner ; If last characters don 't match, then value  is same as the value without last character  in S. ; Else value is obtained considering two cases . a ) All substrings without last character in S b ) All substrings without last characters in both . ; uncomment this to print matrix mat for ( int i = 1 ; i <= m ; i ++ , cout << endl ) for ( int j = 1 ; j <= n ; j ++ ) cout << mat [ i ] [ j ] << " ▁ " ; ; Driver code to check above method
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSubsequenceCount ( string S , string T ) { int m = T . length ( ) , n = S . length ( ) ; if ( m > n ) return 0 ; int mat [ m + 1 ] [ n + 1 ] ; for ( int i = 1 ; i <= m ; i ++ ) mat [ i ] [ 0 ] = 0 ; for ( int j = 0 ; j <= n ; j ++ ) mat [ 0 ] [ j ] = 1 ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { if ( T [ i - 1 ] != S [ j - 1 ] ) mat [ i ] [ j ] = mat [ i ] [ j - 1 ] ; else mat [ i ] [ j ] = mat [ i ] [ j - 1 ] + mat [ i - 1 ] [ j - 1 ] ; } } return mat [ m ] [ n ] ; } int main ( ) { string T = " ge " ; string S = " geeksforgeeks " ; cout << findSubsequenceCount ( S , T ) << endl ; return 0 ; }