sequence.go

     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  // The explicit capacity in s[i:j:j] leads to more efficient code.
    17  
    18  type bytesSeqs struct{ a, b []byte }
    19  
    20  func (s bytesSeqs) lengths() (int, int) { return len(s.a), len(s.b) }
    21  func (s bytesSeqs) commonPrefixLen(ai, aj, bi, bj int) int {
    22  	return commonPrefixLen(s.a[ai:aj:aj], s.b[bi:bj:bj])
    23  }
    24  func (s bytesSeqs) commonSuffixLen(ai, aj, bi, bj int) int {
    25  	return commonSuffixLen(s.a[ai:aj:aj], s.b[bi:bj:bj])
    26  }
    27  
    28  type runesSeqs struct{ a, b []rune }
    29  
    30  func (s runesSeqs) lengths() (int, int) { return len(s.a), len(s.b) }
    31  func (s runesSeqs) commonPrefixLen(ai, aj, bi, bj int) int {
    32  	return commonPrefixLen(s.a[ai:aj:aj], s.b[bi:bj:bj])
    33  }
    34  func (s runesSeqs) commonSuffixLen(ai, aj, bi, bj int) int {
    35  	return commonSuffixLen(s.a[ai:aj:aj], s.b[bi:bj:bj])
    36  }
    37  
    38  type linesSeqs struct{ a, b []string }
    39  
    40  func (s linesSeqs) lengths() (int, int) { return len(s.a), len(s.b) }
    41  func (s linesSeqs) commonPrefixLen(ai, aj, bi, bj int) int {
    42  	return commonPrefixLen(s.a[ai:aj], s.b[bi:bj])
    43  }
    44  func (s linesSeqs) commonSuffixLen(ai, aj, bi, bj int) int {
    45  	return commonSuffixLen(s.a[ai:aj], s.b[bi: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  // commonPrefixLen returns the length of the common prefix of a[ai:aj] and b[bi:bj].
    53  func commonPrefixLen[T comparable](a, b []T) int {
    54  	n := min(len(a), len(b))
    55  	i := 0
    56  	for i < n && a[i] == b[i] {
    57  		i++
    58  	}
    59  	return i
    60  }
    61  
    62  // commonSuffixLen returns the length of the common suffix of a[ai:aj] and b[bi:bj].
    63  func commonSuffixLen[T comparable](a, b []T) int {
    64  	n := min(len(a), len(b))
    65  	i := 0
    66  	for i < n && a[len(a)-1-i] == b[len(b)-1-i] {
    67  		i++
    68  	}
    69  	return i
    70  }
    71
View as plain text