1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
package smetrics
func WagnerFischer(a, b string, icost, dcost, scost int) int {
// Allocate both rows.
row1 := make([]int, len(b)+1)
row2 := make([]int, len(b)+1)
var tmp []int
// Initialize the first row.
for i := 1; i <= len(b); i++ {
row1[i] = i * icost
}
// For each row...
for i := 1; i <= len(a); i++ {
row2[0] = i * dcost
// For each column...
for j := 1; j <= len(b); j++ {
if a[i-1] == b[j-1] {
row2[j] = row1[j-1]
} else {
ins := row2[j-1] + icost
del := row1[j] + dcost
sub := row1[j-1] + scost
if ins < del && ins < sub {
row2[j] = ins
} else if del < sub {
row2[j] = del
} else {
row2[j] = sub
}
}
}
// Swap the rows at the end of each row.
tmp = row1
row1 = row2
row2 = tmp
}
// Because we swapped the rows, the final result is in row1 instead of row2.
return row1[len(row1)-1]
}
|
