1// Copyright 2022 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package lcs
6
7// This file defines the abstract sequence over which the LCS algorithm operates.
8
9// sequences abstracts a pair of sequences, A and B.
10type sequences interface {
11 lengths() (int, int) // len(A), len(B)
12 commonPrefixLen(ai, aj, bi, bj int) int // len(commonPrefix(A[ai:aj], B[bi:bj]))
13 commonSuffixLen(ai, aj, bi, bj int) int // len(commonSuffix(A[ai:aj], B[bi:bj]))
14}
15
16type stringSeqs struct{ a, b string }
17
18func (s stringSeqs) lengths() (int, int) { return len(s.a), len(s.b) }
19func (s stringSeqs) commonPrefixLen(ai, aj, bi, bj int) int {
20 return commonPrefixLenString(s.a[ai:aj], s.b[bi:bj])
21}
22func (s stringSeqs) commonSuffixLen(ai, aj, bi, bj int) int {
23 return commonSuffixLenString(s.a[ai:aj], s.b[bi:bj])
24}
25
26// The explicit capacity in s[i:j:j] leads to more efficient code.
27
28type bytesSeqs struct{ a, b []byte }
29
30func (s bytesSeqs) lengths() (int, int) { return len(s.a), len(s.b) }
31func (s bytesSeqs) commonPrefixLen(ai, aj, bi, bj int) int {
32 return commonPrefixLenBytes(s.a[ai:aj:aj], s.b[bi:bj:bj])
33}
34func (s bytesSeqs) commonSuffixLen(ai, aj, bi, bj int) int {
35 return commonSuffixLenBytes(s.a[ai:aj:aj], s.b[bi:bj:bj])
36}
37
38type runesSeqs struct{ a, b []rune }
39
40func (s runesSeqs) lengths() (int, int) { return len(s.a), len(s.b) }
41func (s runesSeqs) commonPrefixLen(ai, aj, bi, bj int) int {
42 return commonPrefixLenRunes(s.a[ai:aj:aj], s.b[bi:bj:bj])
43}
44func (s runesSeqs) commonSuffixLen(ai, aj, bi, bj int) int {
45 return commonSuffixLenRunes(s.a[ai:aj:aj], s.b[bi:bj:bj])
46}
47
48// TODO(adonovan): optimize these functions using ideas from:
49// - https://go.dev/cl/408116 common.go
50// - https://go.dev/cl/421435 xor_generic.go
51
52// TODO(adonovan): factor using generics when available,
53// but measure performance impact.
54
55// commonPrefixLen* returns the length of the common prefix of a[ai:aj] and b[bi:bj].
56func commonPrefixLenBytes(a, b []byte) int {
57 n := min(len(a), len(b))
58 i := 0
59 for i < n && a[i] == b[i] {
60 i++
61 }
62 return i
63}
64func commonPrefixLenRunes(a, b []rune) int {
65 n := min(len(a), len(b))
66 i := 0
67 for i < n && a[i] == b[i] {
68 i++
69 }
70 return i
71}
72func commonPrefixLenString(a, b string) int {
73 n := min(len(a), len(b))
74 i := 0
75 for i < n && a[i] == b[i] {
76 i++
77 }
78 return i
79}
80
81// commonSuffixLen* returns the length of the common suffix of a[ai:aj] and b[bi:bj].
82func commonSuffixLenBytes(a, b []byte) int {
83 n := min(len(a), len(b))
84 i := 0
85 for i < n && a[len(a)-1-i] == b[len(b)-1-i] {
86 i++
87 }
88 return i
89}
90func commonSuffixLenRunes(a, b []rune) int {
91 n := min(len(a), len(b))
92 i := 0
93 for i < n && a[len(a)-1-i] == b[len(b)-1-i] {
94 i++
95 }
96 return i
97}
98func commonSuffixLenString(a, b string) int {
99 n := min(len(a), len(b))
100 i := 0
101 for i < n && a[len(a)-1-i] == b[len(b)-1-i] {
102 i++
103 }
104 return i
105}
106
107func min(x, y int) int {
108 if x < y {
109 return x
110 } else {
111 return y
112 }
113}