后缀搜索简介：使用Trie树

在后缀Trie中插入单词的伪代码

1void insert(string word)
2{
3    // 将当前节点指向Trie的根节点
4    current_node = root
5
6    // 逆序遍历给定单词中的所有字符
7    for (each char in reversed word)
8    {
9        // 如果当前字符没有对应的子节点
10        // 则创建一个新的子Trie节点
11        if (child_node corresponding to current char is null)
12        {
13            child_node = new TrieNode
14        }
15        // 将当前节点指针移动到子节点
16        current_node = child_node
17    }
18}

在后缀Trie中搜索单词的伪代码

1boolean search(string word)
2{
3    // 将当前节点指向Trie的根节点
4    current_node = root
5
6    // 逆序遍历给定单词中的所有字符
7    for (each char in reversed word)
8    {
9        // 搜索在未检查完键的所有字符前终止。
10        // 这是因为Trie路径在遍历和比较键的所有字符之前就已耗尽，
11        // 表明该键不在Trie中。
12        if (child_node corresponding to current char is null)
13        {
14            return false
15        }
16
17        // 将当前节点指针移动到子节点
18        current_node = child_node
19    }
20
21    // 如果与单词最后一个字符关联的节点的 isEndOfWord 值为 true，
22    // 表示完整的单词存在于Trie中。
23    // 因此返回 true，否则返回 false。
24    if isEndOfWord is true
25        return true
26    else
27        return false
28}

1
2boolean isSuffix(string suff)
3{
4    // 将当前节点指向Trie的根节点
5    current_node = root
6
7    // 逆序遍历给定字符串中的所有字符
8    for (each char in reversed suff)
9    {
10        // 搜索在未检查完键的所有字符前终止。
11        // 这是因为Trie路径在遍历和比较键的所有字符之前就已耗尽，
12        // 表明该键不在Trie中。
13        if (child_node corresponding to current char is null)
14        {
15            return false
16        }
17
18        // 将当前节点指针移动到子节点
19        current_node = child_node
20    }
21
22    // 如果后缀查询字符串的所有字母都成功遍历完毕，
23    // 且搜索过程中未提前终止，说明前缀字符串存在于Trie中。
24    // 因此返回 true。
25    return true
26}