Longest Common Subsequence (Classic Dynamic Programming solution)

gistfile1.go

package main

import "fmt"

func main() {
        a := "GATTACACACT"
	b := "GTCAAACCCCTA"
	fmt.Println(a, len(a), "\t", b, len(b))
	score, val := lcs([]rune(a), []rune(b))
	fmt.Println(score, string(val))
}

func lcs(a, b []rune) (score uint, subseq []rune) {
	A, B := len(a)+1, len(b)+1
	M := make([]uint, A*B)
	for m := range M {
		r, c := m/B, m%B
		if r == 0 || c == 0 {
			M[m] = 0
		} else if a[r-1] == b[c-1] {
			M[m] = M[m-B-1]
			M[m]++
		} else {
			l := M[m-1]
			u := M[m-B]
			if l > u {
				M[m] = l
			} else {
				M[m] = u
			}
		}
	}
	score = M[len(M)-1]
	subseq = backtrack(M, b)
	return
}

func backtrack(M []uint, b []rune) (result []rune) {
	m := len(M) - 1
	B := len(b) + 1
	for m/B > 0 && m%B > 0 {
		c := m % B
		match := (M[m]-1 == M[m-B-1])
		if match {
			result = append(result, b[c-1])
			m -= B
			m--
		} else if M[m] == M[m-1] {
			m--
		} else {
			m -= B
		}
	}
	for i, n := 0, len(result); i < n/2; i++ {
		result[i], result[n-1-i] = result[n-1-i], result[i]
	}
	return
}