生成字符串的所有可能的唯一子字符串

Question

我需要获取字符串的所有唯一子字符串.我已存储串入一个trie,但我不能找出我怎么能使用相同的打印所有例如唯一子

字符串aab所有唯一的子串是{"a", "aa", "aab", "ab", "b"}

这是我的代码 trie

#include <iostream>
#include <map>
#include <string>
#include <stack>

struct trie_node_t {
    typedef std::map<char, trie_node_t *> child_node_t;
    child_node_t m_childMap;
    trie_node_t() :m_childMap(std::map<char, trie_node_t*>()) {}

    void insert( std::string& word ) {
        trie_node_t *pNode = this;
        for ( std::string::const_iterator itr = word.begin(); itr != word.end(); ++itr) {
            char letter = *itr;
            if ( pNode->m_childMap.find(letter) == pNode->m_childMap.end()){
                pNode->m_childMap[letter] = new trie_node_t();
            }
            pNode = pNode->m_childMap[letter];
        }
    }

    void print() {
    }
};

int main ( int argc, char **argv ) {
    trie_node_t trie;
    trie.insert(std::string("aab"));
    trie.print();
}

我如何实现print将打印所有唯一子字符串的函数.

我在寻找 Linear time approach

既然我已经建了trie,有没有什么办法可以遍历,每当我访问任何节点,我可以打印出来作为一个独特的字符串.

Answer 1

首先,构建一个后缀树.这表示字符串的所有后缀,可以在线性时间内完成.由于每个子字符串都是后缀的前缀,因此现在需要枚举后缀的前缀.

幸运的是,如果两个后缀共享一个公共前缀,则前缀将位于来自root的单个公共路径上,因此树中的根(*)和唯一后缀之间的路径之间存在1-1映射.

因此,在后缀树中从根遍历所有路径以产生所有唯一的子串就足够了.

(*)后缀树中的路径被压缩,即边可能代表几个字符.您需要解压缩路径以生成所有子字符串,即将压缩边缘视为多节点路径.