Find the equal pairs of subsequence of S and subsequence of T | Python3 implementation of the approach ; Function to return the pairs of subsequences from S [ ] and subsequences from T [ ] such that both have the same content ; Create dp array ; Base values ; Base values ; Keep previous dp value ; If both elements are same ; Return the required answer ; Driver code
import numpy as np NEW_LINE mod = int ( 1e9 + 7 ) NEW_LINE def subsequence ( S , T , n , m ) : NEW_LINE INDENT dp = np . zeros ( ( n + 1 , m + 1 ) ) ; NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 1 ; NEW_LINE DEDENT for j in range ( m + 1 ) : NEW_LINE INDENT dp [ 0 ] [ j ] = 1 ; NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] - dp [ i - 1 ] [ j - 1 ] ; NEW_LINE if ( S [ i - 1 ] == T [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] ; NEW_LINE DEDENT dp [ i ] [ j ] += mod ; NEW_LINE dp [ i ] [ j ] %= mod ; NEW_LINE DEDENT DEDENT return dp [ n ] [ m ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = [ 1 , 1 ] ; NEW_LINE n = len ( S ) ; NEW_LINE T = [ 1 , 1 ] ; NEW_LINE m = len ( T ) ; NEW_LINE print ( subsequence ( S , T , n , m ) ) ; NEW_LINE DEDENT