Go: Working through the diff algorithms from Myers "An O(ND) Difference Algorithm and Its Variations"

diff.go

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