-
-
Notifications
You must be signed in to change notification settings - Fork 18
/
lcs.go
157 lines (126 loc) · 2.72 KB
/
lcs.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
// Package lcs ...
package lcs
import (
"context"
)
// Indices is the index list of items in xs that forms the LCS between xs and ys.
type Indices []int
// YadLCS returns the x index of each Comparable that are in the YadLCS between x and y.
// The complexity is O(M * log(L)), M is the number of char matches between x and y, L is the length of LCS.
// The worst memory complexity is O(M), but usually it's much less.
//
// The advantage of this algorithm is it's easy to understand and implement. It converts the LCS
// problem into problems that are familiar to us, such as LIS, binary-search, object-recycle, etc., which give us
// more room to do the optimization for each streamline.
func (xs Sequence) YadLCS(ctx context.Context, ys Sequence) Indices {
o := xs.Occurrence(ys)
r := result{list: make([]*node, 0, min(len(xs), len(ys)))}
rest := len(ys)
for _, xi := range o {
if ctx.Err() != nil {
break
}
from := len(r.list)
for _, i := range xi {
from = r.add(from, i, rest)
}
rest--
}
return r.lcs()
}
type node struct {
x int
p *node
c int // pointer count for node recycle
}
func (n *node) link(x int, m *node) {
if m != nil {
m.c++
}
n.p = m
n.x = x
}
type result struct {
list []*node
// reuse node to reduce memory allocation
recycle []*node
}
func (r *result) new(x int, n *node) *node {
var m *node
// reuse node if possible
l := len(r.recycle)
if l > 0 {
m = r.recycle[l-1]
r.recycle = r.recycle[:l-1]
} else {
m = &node{}
}
m.link(x, n)
return m
}
func (r *result) replace(i, x int, n *node) {
// recycle nodes
if m := r.list[i]; m.c == 0 {
for p := m.p; p != nil && p != n; p = p.p {
p.c--
if p.c == 0 {
r.recycle = append(r.recycle, p)
} else {
break
}
}
m.link(x, n)
return
}
r.list[i] = r.new(x, n)
}
func (r *result) add(from, x, rest int) int {
l := len(r.list)
next, n := r.find(from, x)
if n != nil {
if l-next < rest { // only when we have enough rest xs
if next == l {
r.list = append(r.list, r.new(x, n))
} else if x < r.list[next].x {
r.replace(next, x, n)
}
return next
}
}
if l == 0 {
r.list = append(r.list, r.new(x, n))
return 1
}
if l-1 < rest && x < r.list[0].x {
r.replace(0, x, nil)
}
return 0
}
// binary search to find the largest r.list[i].x that is smaller than x
func (r *result) find(from, x int) (int, *node) {
var found *node
for i, j := 0, from; i < j; {
h := (i + j) >> 1
n := r.list[h]
if n.x < x {
from = h
found = n
i = h + 1
} else {
j = h
}
}
return from + 1, found
}
func (r *result) lcs() Indices {
l := len(r.list)
idx := make(Indices, l)
if l == 0 {
return idx
}
for p := r.list[l-1]; p != nil; p = p.p {
l--
idx[l] = p.x
}
return idx
}