File: sa.go

package info (click to toggle)
golang-github-shenwei356-util 0.5.2-1
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 228 kB
  • sloc: makefile: 2
file content (26 lines) | stat: -rw-r--r-- 472 bytes parent folder | download | duplicates (3) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
package sa

import "sort"

// SuffixArray returns the suffix array of s
func SuffixArray(s []byte) []int {
	n := len(s)
	suffixMap := make(map[string]int, n)
	for i := 0; i < n; i++ {
		suffixMap[string(s[i:])] = i
	}
	suffixes := make([]string, n)
	i := 0
	for suffix := range suffixMap {
		suffixes[i] = suffix
		i++
	}
	indice := make([]int, n)
	i = 0
	sort.Strings(suffixes)
	for _, suffix := range suffixes {
		indice[i] = suffixMap[suffix]
		i++
	}
	return indice
}