Implement the function alignStrings in Python. Do not use any library functions. Must be able to read the strings from two files.

Recall that the string alignment problem takes as input two strings x and y, composed of symbols x_i, y_{j element of} , for a fixed symbol set , and returns a minimal-cost set of edit operations for transforming the string x into string y.

Let x contain n_xsymbols, let y contain n_ysymbols, and let the set of edit operations be those defined in the lecture notes (substitution, insertion, deletion, and transposition).

Let the cost of indel be 1, the cost of swap be 10 (plus the cost of the two sub ops), and the cost of sub be 10, except when x_i= y_j, which is a no-op and has cost 0.

alignStrings (x,y) takes as input two ASCII strings x and y, and runs a dynamic programming algorithm to return the cost matrix S, which contains the optimal costs for all the subproblems for aligning these two strings.

alignStrings(x,y) : // x,y are ASCII strings

......S = table of length n_x by n_y // for memoizing the subproblem costs

......initialize S // fill in the basecases

......for i = 1 to nx

..........for j = 1 to ny

................S[ i, j ] = cost( i, j) // optimal cost for x[0...i] and y[0..j]

}}

return S