• ダブル配列を用いたTrie木の接頭辞検索を実装しました

ダブル配列②:構築編の続き。

締めとなる、Trie木の接頭辞検索を実装します。とは言っても与えられた接頭辞までのノードを検索してそこからdfsで検索するだけです。

func (da *doubleArray) SearchPrefix(word string) []string {
    var result []string
    current := indexInt(0)

    for _, code := range da.codes(word)[:len(word)] {
        next := da.base[current] + indexInt(code)

        if int(next) >= len(da.check) || current != da.check[next]-1 {
            return result
        }

        current = next
    }

    da.dfs(current, []byte(word), &result)
    return result
}

func (da *doubleArray) dfs(i indexInt, str []byte, result *[]string) {
    next := da.base[i] + indexInt(da.stopIndex)

    if int(next) < len(da.check) && i == da.check[next]-1 {
        *result = append(*result, string(str))
    }

    for c := codeInt(0); c < da.stopIndex; c++ {
        next := da.base[i] + indexInt(c)

        if int(next) >= len(da.check) || i != da.check[next]-1 {
            continue
        }

        da.dfs(next, append(str, da.toCode(c)), result)
    }
}

ここまでにできた最終形のコードをこちらのgistにおきました。

次はLOUDSを実装してみようかなあ。