Longest Common Subsequence

LCS.py

import sys
test_cases = open(sys.argv[1], 'r')

def generate_char_dict(str):
	char_dict = {}
	for c in str:
		char_dict[c] = char_dict.get(c, 0) + 1
	return char_dict

def LCS(strA, strB):

	len_matrix = [[0 for i in range(0, len(strA) + 1)] \
		for j in range(0, len(strB) + 1)]
	for i in range(1, len(strB) + 1):
		for j in range(1, len(strA) + 1):
			# print '{}, {}'.format(i,j)
			if strA[j-1] == strB[i-1]:
				len_matrix[i][j] = len_matrix[i-1][j-1] + 1
			else:
				len_matrix[i][j] = max(len_matrix[i-1][j], len_matrix[i][j-1])

	# Trace back the result
	seq = ''
	i = len(strB)
	j = len(strA)
	while i > 0 and j > 0:

		if len_matrix[i][j] == len_matrix[i-1][j-1] + 1 and strA[j-1] == strB[i-1]:
			seq = strA[j-1] + seq
			j = j - 1
			i = i - 1
		else:
			if len_matrix[i][j] == len_matrix[i-1][j]:
				i = i - 1
			if len_matrix[i][j] == len_matrix[i][j-1]:
				j = j - 1
	return seq

for test in test_cases:
	strs = test.replace('\n', '')
	strA, strB = strs.split(';')
	print LCS(strA, strB)
test_cases.close()