1// Copyright 2015, Joe Tsai. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE.md file. 4 5// Package sais implements a linear time suffix array algorithm. 6package sais 7 8//go:generate go run sais_gen.go byte sais_byte.go 9//go:generate go run sais_gen.go int sais_int.go 10 11// This package ports the C sais implementation by Yuta Mori. The ports are 12// located in sais_byte.go and sais_int.go, which are identical to each other 13// except for the types. Since Go does not support generics, we use generators to 14// create the two files. 15// 16// References: 17// https://sites.google.com/site/yuta256/sais 18// https://www.researchgate.net/publication/221313676_Linear_Time_Suffix_Array_Construction_Using_D-Critical_Substrings 19// https://www.researchgate.net/publication/224176324_Two_Efficient_Algorithms_for_Linear_Time_Suffix_Array_Construction 20 21// ComputeSA computes the suffix array of t and places the result in sa. 22// Both t and sa must be the same length. 23func ComputeSA(t []byte, sa []int) { 24 if len(sa) != len(t) { 25 panic("mismatching sizes") 26 } 27 computeSA_byte(t, sa, 0, len(t), 256) 28} 29