Build and search a suffix array in Go. Implemented after reading https://blog.nelhage.com/2015/02/regular-expression-search-with-suffix-arrays/

SuffixArray.go

package main

import (
	"bytes"
	"fmt"
	"sort"
)

func main() {

	data := []byte("My name is __!")
	s := BuildSuffixArray(data)

	fmt.Printf("%#v\n", s)

	fmt.Println(s.Contains([]byte("name")))

}

type SuffixArray struct {
	data []byte
	inds []int
}

func (a *SuffixArray) Len() int      { return len(a.inds) }
func (a *SuffixArray) Swap(i, j int) { a.inds[i], a.inds[j] = a.inds[j], a.inds[i] }
func (a *SuffixArray) Less(i, j int) bool {
	return bytes.Compare(a.data[a.inds[i]:], a.data[a.inds[j]:]) < 0
}

func BuildSuffixArray(data []byte) *SuffixArray {

	s := &SuffixArray{data, make([]int, len(data))}
	for i := range s.inds {
		s.inds[i] = i
	}

	sort.Sort(s)

	return s

}

func (s *SuffixArray) Contains(sample []byte) bool {
	i := sort.Search(len(s.inds), func(i int) bool {
		i = s.inds[i] // convert inds index to data index
		return bytes.Compare(sample, s.data[i:i+len(sample)]) <= 0
	})
	if i < len(s.inds) {
		i = s.inds[i] // convert inds index to data index
		return bytes.Equal(sample, s.data[i:i+len(sample)])
	}
	return false
}