| 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 | |
| 5 | package 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. |
| 10 | type 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 | |
| 16 | type stringSeqs struct{ a, b string } |
| 17 | |
| 18 | func (s stringSeqs) lengths() (int, int) { return len(s.a), len(s.b) } |
| 19 | func (s stringSeqs) commonPrefixLen(ai, aj, bi, bj int) int { |
| 20 | return commonPrefixLenString(s.a[ai:aj], s.b[bi:bj]) |
| 21 | } |
| 22 | func (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 | |
| 28 | type bytesSeqs struct{ a, b []byte } |
| 29 | |
| 30 | func (s bytesSeqs) lengths() (int, int) { return len(s.a), len(s.b) } |
| 31 | func (s bytesSeqs) commonPrefixLen(ai, aj, bi, bj int) int { |
| 32 | return commonPrefixLenBytes(s.a[ai:aj:aj], s.b[bi:bj:bj]) |
| 33 | } |
| 34 | func (s bytesSeqs) commonSuffixLen(ai, aj, bi, bj int) int { |
| 35 | return commonSuffixLenBytes(s.a[ai:aj:aj], s.b[bi:bj:bj]) |
| 36 | } |
| 37 | |
| 38 | type runesSeqs struct{ a, b []rune } |
| 39 | |
| 40 | func (s runesSeqs) lengths() (int, int) { return len(s.a), len(s.b) } |
| 41 | func (s runesSeqs) commonPrefixLen(ai, aj, bi, bj int) int { |
| 42 | return commonPrefixLenRunes(s.a[ai:aj:aj], s.b[bi:bj:bj]) |
| 43 | } |
| 44 | func (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]. |
| 56 | func 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 | } |
| 64 | func 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 | } |
| 72 | func 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]. |
| 82 | func 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 | } |
| 90 | func 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 | } |
| 98 | func 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 | |
| 107 | func min(x, y int) int { |
| 108 | if x < y { |
| 109 | return x |
| 110 | } else { |
| 111 | return y |
| 112 | } |
| 113 | } |
| 114 |
Members