# 进行数组D和rec的 填充 for line inrange(1, len(S)+1): for column inrange(1, len(T)+1): # 一下两步是为了确定LU(替换) 操作是否需要替换操作 如果该元素相同的话则需要 +1操作, 如果不需要替换则不需要加一操作 c = 1 if S[line - 1] == T[column - 1]: c = 0
# 进行各种操作的赋值 LU = D[line - 1][column - 1] + c L = D[line][column-1] + 1 U = D[line - 1][column] + 1
# 我们的先后顺序是 先替换 后左 在上 if LU <= L and LU <= U: D[line][column] = LU rec[line][column] = "LU" elif L <= LU and L <= U: D[line][column] = L rec[line][column] = "L" elif U <= LU and U <= L: D[line][column] = U rec[line][column] = "U"
# 初始化数组D Rec definit_d_rec(S, T): line = len(S) + 1 column = len(T) + 1 D = [ [ [] for m inrange(column)] for i inrange(line)] rec = [ [ [] for m inrange(column)] for i inrange(line)]
for l inrange(line): D[l][0] = l rec[l][0] = 'U' for c inrange(column): D[0][c] = c rec[0][c] = 'L' return D, rec
S = "ABCBDAB" T = "BDCABA"
D, rec = init_d_rec(S, T)
mid_edit_distance(S, T, D, rec)
for line in D: for column in line: print(column, end = "\t") print()