#NEWLINE# def longest_common_subsequence( x , y ) : #NEWLINE# #INDENT# 'Longest common subsequence\n\n    Dynamic programming\n\n    :param x:\n    :param y: x,y are lists or strings\n    :returns: longest common subsequence in form of a string\n    :complexity: `O(|x|*|y|)`\n    ' #NEWLINE# n = len ( x ) #NEWLINE# m = len ( y ) #NEWLINE# A = [ [ 0 for j in range ( ( m + 1 ) ) ] for i in range ( ( n + 1 ) ) ] #NEWLINE# for i in range ( n ) : #NEWLINE# #INDENT# for j in range ( m ) : #NEWLINE# #INDENT# if ( x [ i ] == y [ j ] ) : #NEWLINE# #INDENT# A [ ( i + 1 ) ] [ ( j + 1 ) ] = ( A [ i ] [ j ] + 1 ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# A [ ( i + 1 ) ] [ ( j + 1 ) ] = max ( A [ i ] [ ( j + 1 ) ] , A [ ( i + 1 ) ] [ j ] ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# sol = [ ] #NEWLINE# ( i , j ) = ( n , m ) #NEWLINE# while ( A [ i ] [ j ] > 0 ) : #NEWLINE# #INDENT# if ( A [ i ] [ j ] == A [ ( i - 1 ) ] [ j ] ) : #NEWLINE# #INDENT# i -= 1 #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( A [ i ] [ j ] == A [ i ] [ ( j - 1 ) ] ) : #NEWLINE# #INDENT# j -= 1 #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# i -= 1 #NEWLINE# j -= 1 #NEWLINE# sol . append ( x [ i ] ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# return '' . join ( sol [ : : ( - 1 ) ] )