<s> """<STR_LIT>""" <EOL> def longest_common_subsequence ( s1 , s2 ) : <EOL> m , n = len ( s1 ) , len ( s2 ) <EOL> cache = [ [ <NUM_LIT:0> for j in range ( n + <NUM_LIT:1> ) ] for i in range ( m + <NUM_LIT:1> ) ] <EOL> for i , character_s1 in enumerate ( s1 ) : <EOL> for j , character_s2 in enumerate ( s2 ) : <EOL> if character_s1 == character_s2 : <EOL> cache [ i + <NUM_LIT:1> ] [ j + <NUM_LIT:1> ] = cache [ i ] [ j ] + <NUM_LIT:1> <EOL> else : <EOL> cache [ i + <NUM_LIT:1> ] [ j + <NUM_LIT:1> ] = max ( cache [ i ] [ j + <NUM_LIT:1> ] , cache [ i + <NUM_LIT:1> ] [ j ] ) <EOL> sequence = "<STR_LIT>" <EOL> i , j = m , n <EOL> while i >= <NUM_LIT:1> and j >= <NUM_LIT:1> : <EOL> if s1 [ i - <NUM_LIT:1> ] == s2 [ j - <NUM_LIT:1> ] : <EOL> sequence += s1 [ i - <NUM_LIT:1> ] <EOL> i , j = i - <NUM_LIT:1> , j - <NUM_LIT:1> <EOL> elif cache [ i - <NUM_LIT:1> ] [ j ] > cache [ i ] [ j - <NUM_LIT:1> ] : <EOL> i -= <NUM_LIT:1> <EOL> else : <EOL> j -= <NUM_LIT:1> <EOL> return ( len ( sequence ) , sequence [ : : - <NUM_LIT:1> ] ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> print ( longest_common_subsequence ( "<STR_LIT>" , "<STR_LIT>" ) ) </s>
