Count ways to increase LCS length of two strings by one | Python3 program to get number of ways to increase LCS by 1 ; Method returns total ways to increase LCS length by 1 ; Fill positions of each character in vector vector < int > position [ M ] ; ; Initializing 2D array by 0 values ; Filling LCS array for prefix substrings ; Filling LCS array for suffix substrings ; Looping for all possible insertion positions in first string ; Trying all possible lower case characters ; Now for each character , loop over same character positions in second string ; If both , left and right substrings make total LCS then increase result by 1 ; Driver code to test above methods
M = 26 NEW_LINE def waysToIncreaseLCSBy1 ( str1 , str2 ) : NEW_LINE INDENT m = len ( str1 ) NEW_LINE n = len ( str2 ) NEW_LINE position = [ [ ] for i in range ( M ) ] NEW_LINE for i in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT position [ ord ( str2 [ i - 1 ] ) - 97 ] . append ( i ) NEW_LINE DEDENT lcsl = [ [ 0 for i in range ( n + 2 ) ] for j in range ( m + 2 ) ] NEW_LINE lcsr = [ [ 0 for i in range ( n + 2 ) ] for j in range ( m + 2 ) ] NEW_LINE for i in range ( 1 , m + 1 , 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT if ( str1 [ i - 1 ] == str2 [ j - 1 ] ) : NEW_LINE INDENT lcsl [ i ] [ j ] = 1 + lcsl [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lcsl [ i ] [ j ] = max ( lcsl [ i - 1 ] [ j ] , lcsl [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( m , 0 , - 1 ) : NEW_LINE INDENT for j in range ( n , 0 , - 1 ) : NEW_LINE INDENT if ( str1 [ i - 1 ] == str2 [ j - 1 ] ) : NEW_LINE INDENT lcsr [ i ] [ j ] = 1 + lcsr [ i + 1 ] [ j + 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lcsr [ i ] [ j ] = max ( lcsr [ i + 1 ] [ j ] , lcsr [ i ] [ j + 1 ] ) NEW_LINE DEDENT DEDENT DEDENT ways = 0 NEW_LINE for i in range ( 0 , m + 1 , 1 ) : NEW_LINE INDENT for C in range ( 0 , 26 , 1 ) : NEW_LINE INDENT for j in range ( 0 , len ( position [ C ] ) , 1 ) : NEW_LINE INDENT p = position [ C ] [ j ] NEW_LINE if ( lcsl [ i ] [ p - 1 ] + lcsr [ i + 1 ] [ p + 1 ] == lcsl [ m ] [ n ] ) : NEW_LINE INDENT ways += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT return ways NEW_LINE DEDENT str1 = " abcabc " NEW_LINE str2 = " abcd " NEW_LINE print ( waysToIncreaseLCSBy1 ( str1 , str2 ) ) NEW_LINE