README.md
1# Go Longest Common Subsequence (LCS)
2
3[![GoDoc](https://godoc.org/github.com/yudai/golcs?status.svg)][godoc]
4[![MIT License](http://img.shields.io/badge/license-MIT-blue.svg)][license]
5
6[godoc]: https://godoc.org/github.com/yudai/golcs
7[license]: https://github.com/yudai/golcs/blob/master/LICENSE
8
9A package to calculate [LCS](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) of slices.
10
11## Usage
12
13```sh
14go get github.com/yudai/golcs
15```
16
17```go
18import " github.com/yudai/golcs"
19
20left = []interface{}{1, 2, 5, 3, 1, 1, 5, 8, 3}
21right = []interface{}{1, 2, 3, 3, 4, 4, 5, 1, 6}
22
23lcs := golcs.New(left, right)
24
25lcs.Values() // LCS values => []interface{}{1, 2, 5, 1}
26lcs.IndexPairs() // Matched indices => [{Left: 0, Right: 0}, {Left: 1, Right: 1}, {Left: 2, Right: 6}, {Left: 4, Right: 7}]
27lcs.Length() // Matched length => 4
28
29lcs.Table() // Memo table
30```
31
32All 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.
33
34
35## FAQ
36
37### How can I give `[]byte` values to `Lcs()` as its arguments?
38
39As `[]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).
40
41```go
42leftBytes := []byte("TGAGTA")
43left = make([]interface{}, len(leftBytes))
44for i, v := range leftBytes {
45 left[i] = v
46}
47
48rightBytes := []byte("GATA")
49right = make([]interface{}, len(rightBytes))
50for i, v := range rightBytes {
51 right[i] = v
52}
53
54lcs.New(left, right)
55```
56
57
58## LICENSE
59
60The MIT license (See `LICENSE` for detail)
61