c++ - 后缀范围 c++

Question

我正在尝试构建一个后缀范围

如果我有字符串 "catalog""catalyst""ban""bany"

那么后缀树会是这样的

                            .
                           / \
                          c   b
                         /     \
                        a       a
                       /         \
                      t           n
                     / \         / \        
                    a   a       $   y 
                   /     \         / \
                  l       l       $    $
                 /         \
                o           y         
               /             \
              g               s
             / \               \
            $   $               t
                                /\
                               $   $

我现在想找到每个字符串的后缀范围 .. 如果我使用字符串“Cat”，那么它应该给我一个包含所有后缀的范围，其中“cat”是前缀。我需要使用哨兵来分隔每个字符串..可能是一个“$”

谁能建议我使用 c++ 找出这个问题的最佳方法。任何引用资料都会有所帮助。谢谢

Answer 1

比我的第一个答案简单得多。你有一个 std::set 字符串:

typedef std::set<std::string>::iterator iter_type;
std::set<std::string> data;

和一个名为 find() 的函数，它返回一对迭代器。第一个迭代器指向匹配前缀的字符串的开头，最后一个迭代器指向匹配前缀的最后一个字符串。如果您有 10000 个字符串，这只需要检查其中的大约 26 个。

std::pair<iter_type, iter_type> find(std::string substr) {
   std::pair<iter_type, iter_type> r;
   r.first = data.lower_bound(substr);
   substr[substr.size()-1]++; //I'm assuming substr is at least one character
   r.second = data.upper_bound(substr);
   return r;
}

然后，在加载数据后，您只需调用 find(...) 函数，它就会返回一对指向您想要的字符串的迭代器。您可以将这些用作任何标准算法的输入，或做任何事情。

int main() {
    data.insert("catalog");
    data.insert("catalyst");
    data.insert("ban");
    data.insert("bany");
    //find the region of strings beginning with "cat"
    std::pair<iter_type, iter_type> range = find("cat");
    //display them all
    for(iter_type i=range.first; i!=range.second; ++i)
        std::cout << *i << '\n';
}