Skip to content
/ golcs Public
forked from yudai/golcs

Go Longest Common Subsequence

License

Notifications You must be signed in to change notification settings

meghb/golcs

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Go Longest Common Subsequence (LCS)

GoDoc MIT License

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)

About

Go Longest Common Subsequence

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Go 100.0%