Count distinct occurrences as a subsequence | Python3 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 . x 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 . ; Driver Code
def findSubsequenceCount ( S , T ) : NEW_LINE INDENT m = len ( T ) NEW_LINE n = len ( S ) NEW_LINE if m > n : NEW_LINE INDENT return 0 NEW_LINE DEDENT mat = [ [ 0 for _ in range ( n + 1 ) ] for __ in range ( m + 1 ) ] NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT mat [ i ] [ 0 ] = 0 NEW_LINE DEDENT for j in range ( n + 1 ) : NEW_LINE INDENT mat [ 0 ] [ j ] = 1 NEW_LINE DEDENT for i in range ( 1 , m + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if T [ i - 1 ] != S [ j - 1 ] : NEW_LINE INDENT mat [ i ] [ j ] = mat [ i ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT mat [ i ] [ j ] = ( mat [ i ] [ j - 1 ] + mat [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return mat [ m ] [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT T = " ge " NEW_LINE S = " geeksforgeeks " NEW_LINE print ( findSubsequenceCount ( S , T ) ) NEW_LINE DEDENT