4

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

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

然后后缀树就像

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

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

任何人都可以建议我使用 c++ 找出这一点的最佳方法。任何参考资料都会有所帮助。谢谢你

4

4 回答 4

2

比我的第一个简单得多的答案。你有一个 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';
}
于 2011-08-23T19:37:39.110 回答
1

解决方案1：节省空间使用Trie数据结构（一个字符是一个节点，一个节点可以指向26个不同的节点）找到给定前缀的最后一个节点。print prefix+'所有终端节点的路径'

解决方案 2：节省时间说您只对前 3 个前缀字符感兴趣。创建一个 3d 数组

 vector<string> arr[27][27][27]

插入 。如果要插入
单词：ABCD arr[A][B][C].push_back("D") 单词：BBBX arr[B][B][B].push_back("X")

打印：vector & a = arr[char1][char2][char3] for( string s in a) char1-char2-char3+ s

于 2011-08-23T19:38:31.187 回答
0

我想这是最简洁的答案。:)

set<string> s;
string word = "ABC"
//Inserts.
// e.g. s.insert("ABCD");

for(set<string>::iterator it=s.begin();it!=s.end();++it)
    if(!(*it).compare(0,word.size(),word))
        cout<<*it<<endl;

测试代码！:P

于 2011-08-24T17:53:37.997 回答
0

我发布了一个算法来解决一个非常相似的问题，是否有合适的数据结构来解决这个问题？. 首先，我们创建一个节点的后缀树，类似于

class node { //create a prefix node type
    node & operator=(const node & b); //UNDEFINED, NO COPY
    node & operator=(const node && b); //UNDEFINED, NO COPY
    node * next[27];  // pointers to nodes of the next letter (27th letter is $)
public:
    node(); 
    ~node();
    void add(char* mystring);
    void find(char* mystring, 
        std::vector<std::pair<int, std::string>>& out, 
        std::string sofar="");
}root;

并填充它。然后，为了找到“cata”的所有子字符串，我们根据“cata”中的字母（root[3]->[0]->['t'-'a'?]->[ 0])，并跟踪字符串sofar。当我们到达末尾时mystring，我们递归地尝试向下遍历每个孩子，而不仅仅是匹配子字符串的孩子，并且在我们找到“end”（字母 27）的任何地方，我们推sofar入out。然后我们简单地返回，并out保存所有以“cata”开头的完整字符串。

于 2011-08-23T19:19:31.917 回答