Go Longest Common Subsequence (LCS)
A package to calculate LCS of slices.
Usage
go get github.com/yudai/golcsimport " github.com/yudai/golcs"
left = []interface{}{1, 2, 5, 3, 1, 1, 5, 8, 3}
right = []interface{}{1, 2, 3, 3, 4, 4, 5, 1, 6}
lcs := golcs.New(left, right)
lcs.Values() // LCS values => []interface{}{1, 2, 5, 1}
lcs.IndexPairs() // Matched indices => [{Left: 0, Right: 0}, {Left: 1, Right: 1}, {Left: 2, Right: 6}, {Left: 4, Right: 7}]
lcs.Length() // Matched length => 4
lcs.Table() // Memo tableAll the methods of Lcs cache their return values. For example, the memo table is calculated only once and reused when Values(), Length() and other methods are called.
FAQ
How can I give []byte values to Lcs() as its arguments?
As []interface{} is incompatible with []othertype like []byte, you need to create a []interface{} slice and copy the values in your []byte slice into it. Unfortunately, Go doesn't provide any mesure to cast a slice into []interface{} with zero cost. Your copy costs O(n).
leftBytes := []byte("TGAGTA")
left = make([]interface{}, len(leftBytes))
for i, v := range leftBytes {
left[i] = v
}
rightBytes := []byte("GATA")
right = make([]interface{}, len(rightBytes))
for i, v := range rightBytes {
right[i] = v
}
lcs.New(left, right)LICENSE
The MIT license (See LICENSE for detail)