Go言語の標準ライブラリをぱらぱらっとみていたら気になる物が
index/suffixarray
その名の通り接尾辞配列(Suffix Array)実装ですね。 こんなものが標準で組み込まれているなんてさすがGoogle製。
(ちなみに以前Javaで実装してました)
suffixarray.New([]byte)
でインデックスをビルドして、
Lookup([]byte, int)
で検索。第2引数は最大取得件数で-1にすれば全件取得。
返り値は第1引数の文字列から始まる部分文字列の位置の配列。
試してみた。
package main
import (
"fmt"
"index/suffixarray"
)
func main() {
input := "abracadabra"
index := suffixarray.New([]byte(input))
// "abracadabra"のうちraから始まる文字列を表示
fmt.Println("begin from 'ra'")
fmt.Print("\t")
for _, value := range index.Lookup([]byte("ra"), -1) {
fmt.Print(input[value:], " ")
}
fmt.Println()
// "abracadabra"のうちabから始まる文字列を表示
fmt.Println("begin from 'ab'")
fmt.Print("\t")
for _, value := range index.Lookup([]byte("ab"), -1) {
fmt.Print(input[value:], " ")
}
fmt.Println()
// "abracadabra"のうちbrから始まる文字列を表示
fmt.Println("begin from 'br'")
fmt.Print("\t")
for _, value := range index.Lookup([]byte("br"), -1) {
fmt.Print(input[value:], " ")
}
fmt.Println()
}
実行結果
$ go run suffixarray.go
begin from 'ra'
ra racadabra
begin from 'ab'
abra abracadabra
begin from 'br'
bra bracadabra
Javaのときと同じですね。
Suffix Arrayの初歩について学ぶには↓がおすすめです。
「続・アルゴリズムを学ぼう」にも解説されているらしい。