README
¶
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
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)
Documentation
¶
Overview ¶
package lcs provides functions to calculate Longest Common Subsequence (LCS) values from two arbitrary arrays.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IndexPair ¶
IndexPair represents an pair of indeices in the Left and Right arrays found in the LCS value.
type Lcs ¶
type Lcs interface {
// Values calculates the LCS value of the two arrays.
Values() (values []interface{})
// ValueContext is a context aware version of Values()
ValuesContext(ctx context.Context) (values []interface{}, err error)
// IndexPairs calculates paris of indices which have the same value in LCS.
IndexPairs() (pairs []IndexPair)
// IndexPairsContext is a context aware version of IndexPairs()
IndexPairsContext(ctx context.Context) (pairs []IndexPair, err error)
// Length calculates the length of the LCS.
Length() (length int)
// LengthContext is a context aware version of Length()
LengthContext(ctx context.Context) (length int, err error)
// Left returns one of the two arrays to be compared.
Left() (leftValues []interface{})
// Right returns the other of the two arrays to be compared.
Right() (righttValues []interface{})
}
Lcs is the interface to calculate the LCS of two arrays.
Source Files