Package suffixarray implements substring search in logarithmic time using an
in-memory suffix array.

Example use:

Package files

suffixarray.go

  1. type Index struct {
  2. }

Index implements a suffix array for fast substring search.

  1. func New(data []) *Index

New creates a new Index for data. Index creation time is O(N*log(N)) for N =
len(data).

func (*Index)

Bytes returns the data over which the index was created. It must not be
modified.

  1. func (x *) FindAllIndex(r *regexp., n int) (result [][])

FindAllIndex returns a sorted list of non-overlapping matches of the regular
expression r, where a match is a pair of indices specifying the matched slice of
x.Bytes(). If n < 0, all matches are returned in successive order. Otherwise, at
most n matches are returned and they may not be successive. The result is nil if
there are no matches, or if n == 0.

func (*Index) Lookup

  1. func (x *Index) Lookup(s [], n int) (result [])

Lookup returns an unsorted list of at most n indices where the byte string s
occurs in the indexed data. If n < 0, all occurrences are returned. The result
is nil if s is empty, s is not found, or n == 0. Lookup time is O(log(N)*len(s)

  • len(result)) where N is the size of the indexed data.


Example:

  1. func (x *) Read(r io.) error

Read reads the index from r into x; x must not be nil.

func (*Index)

    Write writes the index x to w.