Instantly share code, notes, and snippets.

# ae6up/diff.go Created Apr 20, 2013

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)) }