Skip to content

Instantly share code, notes, and snippets.

@ae6up ae6up/diff.go
Created Apr 20, 2013

Embed
What would you like to do?
Go: Working through the diff algorithms from Myers "An O(ND) Difference Algorithm and Its Variations"
package main
import "fmt"
/*******************************************************************************
* Reference:
* An O(ND) Difference Algorithm and Its Variations
* Eugene W. Myers
*******************************************************************************/
func fig2(a, b string) (d int) {
m, n := len(b)-1, len(a)-1
max := m + n
v := make([]int, (max*2)+1)
for d = 0; d < max; d++ {
for k := -d; k <= d; k = k + 2 {
var x, y int
fmt.Printf("d=%v, k=%v\n", d, k)
if k == -d || k != d && v[max+k-1] < v[max+k+1] {
x = v[max+k+1]
} else {
x = v[max+k-1] + 1
}
y = x - k
fmt.Printf("(%v, %v)\n", x, y)
for x < n && y < m && a[x+1] == b[y+1] {
x, y = x+1, y+1
fmt.Printf("(%v, %v)\n", x, y)
}
v[max+k] = x
fmt.Println(v)
if x >= n && y >= m {
// then we have found the shortest path
return
}
}
}
// length is longer than max shouldn't get here
fmt.Println(v)
return -1
}
func main() {
a, b := " abcabba", " cbabac"
fmt.Println(fig2(a, b))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.