アルゴリズムクイックリファレンス 第2版

3.6

 一般的なアプローチ

■

55

for j in range(1, len2+1):

m[0][j] = j

for i in range(1, len1+1):

m[i][0] = i

#

最良を計算する

for i in range(1,len1+1):

for j in range(1,len2+1):

cost = 1

if s1[i-1] == s2[j-1]: cost = 0

replaceCost = m[i-1][j-1] + cost

removeCost = m[i-1][j] + 1

insertCost = m[i][j-1] + 1

costs = [replaceCost,removeCost,insertCost]

m[i][j] = min(costs)

op[

i][j] = costs.index(m[i][j])

ops = []

i = len1

j = len2

while i != 0 or j != 0:

if op[i][j] == REMOVE or j == 0:

ops.append('remove {}-th char {} of {}'.format(i,s1[i-1],s1))

i = i-1

elif op[i][j] == INSERT or i == 0:

ops.append('insert {}-th char {} of {}'.format(j,s2[j-1],s2))

j = j-1

else: ...