IK.AM

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の初歩について学ぶには↓がおすすめです。

「続・アルゴリズムを学ぼう」にも解説されているらしい。