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

Question

我需要获取字符串的所有唯一子字符串。我已将字符串存储到 trie 中，但我无法弄清楚如何使用它来打印所有唯一的子字符串例如

string 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 函数。

我正在寻找线性时间方法

自从我构建了一个 trie 之后，有什么方法可以让我遍历并且每当我访问任何节点时我都可以将它打印为一个唯一的字符串。

Answer 1

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

幸运的是，如果两个后缀共享一个公共(public)前缀，则该前缀将位于从根开始的单个公共(public)路径上，因此树中从根 (*) 开始的路径与唯一后缀之间存在 1-1 映射。

因此，从后缀树中的根开始遍历所有路径以生成所有唯一子字符串就足够了。

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