在golang中创建后缀树

Question

我有一个字符串数组,我需要在Golang中创建一个后缀树.Golang中的SuffixArray不能满足我的需求,因为它只接受字节数组(即单个字符串).任何人都可以提供实施指针.提前致谢.

Answer 1

以下是如何使用后缀数组执行自动完成的示例.(游乐场).

请注意,我将所有字符串加在一起,其前缀\x00不能首先出现在字符串中.

package main

import (
    "fmt"
    "index/suffixarray"
    "regexp"
    "strings"
)

func main() {
    words := []string{
        "aardvark",
        "happy",
        "hello",
        "hero",
        "he",
        "hotel",
    }
    // use \x00 to start each string
    joinedStrings := "\x00" + strings.Join(words, "\x00")
    sa := suffixarray.New([]byte(joinedStrings))

    // User has typed in "he"
    match, err := regexp.Compile("\x00he[^\x00]*")
    if err != nil {
        panic(err)
    }
    ms := sa.FindAllIndex(match, -1)

    for _, m := range ms {
        start, end := m[0], m[1]
        fmt.Printf("match = %q\n", joinedStrings[start+1:end])
    }
}

打印

match = "hello"
match = "hero"
match = "he"