Number of ways to insert a character to increase the LCS by one | Python Program to Number of ways to insert a character to increase LCS by one ; Return the Number of ways to insert a character to increase the Longest Common Subsequence by one ; Insert all positions of all characters in string B ; Longest Common Subsequence ; Longest Common Subsequence from reverse ; inserting character between position i and i + 1 ; Driver Code
MAX = 256 NEW_LINE def numberofways ( A , B , N , M ) : NEW_LINE INDENT pos = [ [ ] for _ in range ( MAX ) ] NEW_LINE for i in range ( M ) : NEW_LINE INDENT pos [ ord ( B [ i ] ) ] . append ( i + 1 ) NEW_LINE DEDENT dpl = [ [ 0 ] * ( M + 2 ) for _ in range ( N + 2 ) ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( 1 , M + 1 ) : NEW_LINE INDENT if A [ i - 1 ] == B [ j - 1 ] : NEW_LINE INDENT dpl [ i ] [ j ] = dpl [ i - 1 ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dpl [ i ] [ j ] = max ( dpl [ i - 1 ] [ j ] , dpl [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT LCS = dpl [ N ] [ M ] NEW_LINE dpr = [ [ 0 ] * ( M + 2 ) for _ in range ( N + 2 ) ] NEW_LINE for i in range ( N , 0 , - 1 ) : NEW_LINE INDENT for j in range ( M , 0 , - 1 ) : NEW_LINE INDENT if A [ i - 1 ] == B [ j - 1 ] : NEW_LINE INDENT dpr [ i ] [ j ] = dpr [ i + 1 ] [ j + 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dpr [ i ] [ j ] = max ( dpr [ i + 1 ] [ j ] , dpr [ i ] [ j + 1 ] ) NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT for j in range ( MAX ) : NEW_LINE INDENT for x in pos [ j ] : NEW_LINE INDENT if dpl [ i ] [ x - 1 ] + dpr [ i + 1 ] [ x + 1 ] == LCS : NEW_LINE INDENT ans += 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = " aa " NEW_LINE B = " baaa " NEW_LINE N = len ( A ) NEW_LINE M = len ( B ) NEW_LINE print ( numberofways ( A , B , N , M ) ) NEW_LINE DEDENT