README.md
1.7 KB
Go Longest Common Subsequence (LCS)
A package to calculate LCS of slices.
Usage
go get github.com/yudai/golcs
import " 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 table
All 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
[]byte
values to Lcs()
as its arguments?
How can I give 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)