lcs

package
v0.31.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 20, 2022 License: MIT Imports: 5 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var SplitKey = struct{}{}

SplitKey for context

Functions

func Split 

func Split(s string) []string

Split a line into words

Types

type Comparable 

type Comparable interface {
	// String for comparison, such as the hash
	String() string
}

Comparable interface

type Element 

type Element string

Element of a line, a word, or a character

func (Element) String 

func (e Element) String() string

String returns the full content

type Sequence 

type Sequence []Comparable

Sequence list

func NewChars 

func NewChars(s string) Sequence

NewChars from string

func NewLines 

func NewLines(s string) Sequence

NewLines from string. It will split the s via newlines.

func NewWords 

func NewWords(words []string) Sequence

NewWords from string list

func StandardLCS 

func StandardLCS(xs, ys Sequence) Sequence

StandardLCS implementation for testing purpose only, because it's very inefficient. https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined.

func (Sequence) Histogram 

func (xs Sequence) Histogram() map[string][]int

Histogram of each Comparable

func (Sequence) IsSubsequenceOf 

func (xs Sequence) IsSubsequenceOf(ys Sequence) bool

IsSubsequenceOf returns true if x is a subsequence of y

func (Sequence) String 

func (xs Sequence) String() string

String interface

func (Sequence) Sub 

func (xs Sequence) Sub(list []int) Sequence

Sub from indexes

func (Sequence) YadLCS 

func (xs Sequence) YadLCS(ctx context.Context, ys Sequence) []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 YadLCS. The worst memory complexity is O(M), usually it's much less.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.