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
|
// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package lcs
import (
"fmt"
)
// For each D, vec[D] has length D+1,
// and the label for (D, k) is stored in vec[D][(D+k)/2].
type label struct {
vec [][]int
}
// Temporary checking DO NOT COMMIT true TO PRODUCTION CODE
const debug = false
// debugging. check that the (d,k) pair is valid
// (that is, -d<=k<=d and d+k even)
func checkDK(D, k int) {
if k >= -D && k <= D && (D+k)%2 == 0 {
return
}
panic(fmt.Sprintf("out of range, d=%d,k=%d", D, k))
}
func (t *label) set(D, k, x int) {
if debug {
checkDK(D, k)
}
for len(t.vec) <= D {
t.vec = append(t.vec, nil)
}
if t.vec[D] == nil {
t.vec[D] = make([]int, D+1)
}
t.vec[D][(D+k)/2] = x // known that D+k is even
}
func (t *label) get(d, k int) int {
if debug {
checkDK(d, k)
}
return int(t.vec[d][(d+k)/2])
}
func newtriang(limit int) label {
if limit < 100 {
// Preallocate if limit is not large.
return label{vec: make([][]int, limit)}
}
return label{}
}
|
