Golang - Longest Common Subsequence

lcs.go

package main

import "fmt"

func main() {
	x := "ACCGGGTTACCGTTTAAAACCCGGGTAACCT"
	y := "CCAGGACCAGGGACCGTTTACCAGCCTTAAACCA"
	n := len(x)
	m := len(y)

	tb := make([][]int, n+1)
	meta := make([][]rune, n+1)
	for i := range tb {
		tb[i] = make([]int, m+1)
		meta[i] = make([]rune, m+1)
		tb[i][0] = 0
	}
	for j := range tb[0] {
		tb[0][j] = 0
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if x[i-1] == y[j-1] {
				tb[i][j] = tb[i-1][j-1] + 1
				meta[i][j] = 's'
			} else {
				if tb[i][j-1] > tb[i-1][j] {
					tb[i][j] = tb[i][j-1]
					meta[i][j] = 'j'
				} else {
					tb[i][j] = tb[i-1][j]
					meta[i][j] = 'i'
				}
			}
		}
	}

	fmt.Println(tb[n][m])
	printLCS(meta, x, n, m)
	fmt.Println()
}

func printLCS(meta [][]rune, x string, i int, j int) {
	if i == 0 || j == 0 {
		return
	}

	switch meta[i][j] {
	case 's':
		printLCS(meta, x, i-1, j-1)
		fmt.Print(string(x[i-1]))
	case 'j':
		printLCS(meta, x, i, j-1)
	case 'i':
		printLCS(meta, x, i-1, j)
	}
}