1632
правки
Изменения
м
rollbackEdits.php mass rollback
A = \left\{\begin{array}{llcl}
0&;\ i = 0,\ j = 0\\
i* deleteCost&;\ j = 0,\ i > 0\\j* insertCost&;\ i = 0,\ j > 0\\
D(i - 1, j - 1)&;\ S[i] = T[j]\\
\min{(}\\
'''int''' DamerauLevenshteinDistance(S: '''char[1..M]''', T: '''char[1..N]'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''):
d: '''int[0..M][0..N]'''
''<font color=green>// База динамики</font>''
d[0][0] = 0 '''for''' i = 0 1 '''to''' M d[i][0] = d[i- 1][0] + deleteCost
'''for''' j = 1 '''to''' N
d[0][j] = d[0][j- 1] + insertCost
'''for''' i = 1 '''to''' M
A = \left\{\begin{array}{llcl}
0&;\ i = 0,\ j = 0\\
i* deleteCost&;\ j = 0,\ i > 0\\j* insertCost&;\ i = 0,\ j > 0\\
D(i - 1, j - 1)&;\ S[i] = T[j]\\
\min{(}\\
'''return''' M
D: '''int[0..M + 1][0..N + 1]''' ''<font color=green>// Динамика</font>''
INF = (M + N ) * max(deleteCost, insertCost, replaceCost, transposeCost) ''<font color=green>// Большая константа</font>''
''<font color=green>// База индукции</font>''
D[0][0] = INF
'''for''' i = 0 '''to''' M
D[i + 1][1] = i* deleteCost
D[i + 1][0] = INF
'''for''' j = 0 '''to''' N
D[1][j + 1] = j* insertCost
D[0][j + 1] = INF
lastPosition[S[i]] = i
'''return''' D[M + 1][N + 1]
==См. также==
