Find number of times a string occurs as a subsequence in given string | Iterative DP function to find the number of times the second string occurs in the first string , whether continuous or discontinuous ; Create a table to store results of sub - problems ; If first string is empty ; If second string is empty ; Fill lookup [ ] [ ] in bottom up manner ; If last characters are same , we have two options - 1. consider last characters of both strings in solution 2. ignore last character of first string ; If last character are different , ignore last character of first string ; Driver code
def count ( a , b ) : NEW_LINE INDENT m = len ( a ) NEW_LINE n = len ( b ) NEW_LINE lookup = [ [ 0 ] * ( n + 1 ) for i in range ( m + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT lookup [ 0 ] [ i ] = 0 NEW_LINE DEDENT for i in range ( m + 1 ) : NEW_LINE INDENT lookup [ i ] [ 0 ] = 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 a [ i - 1 ] == b [ j - 1 ] : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i - 1 ] [ j - 1 ] + lookup [ i - 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT return lookup [ m ] [ n ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = " GeeksforGeeks " NEW_LINE b = " Gks " NEW_LINE print ( count ( a , b ) ) NEW_LINE DEDENT