генерировать все возможные уникальные подстроки строки

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, которая будет печатать всю уникальную подстроку.

Я ищу Linear time approach

Поскольку я построил trie, есть ли способ, с помощью которого я могу выполнить итерацию, и всякий раз, когда я посещаю какой-либо узел, я могу напечатать его как уникальную строку.

Answer 1

Сначала создайте дерево суффиксов.Это представляет все суффиксы строки и может быть сделано за линейное время.Поскольку каждая подстрока является префиксом суффикса, теперь вам нужно перечислить префиксы суффиксов.

К счастью, если два суффикса имеют общий префикс, префикс будет находиться по одному общему пути от root, поэтому между путями от root (*) в дереве и уникальными суффиксами есть соответствие 1-1.

Поэтому достаточно перебрать все пути от корня в дереве суффиксов, чтобы получить все уникальные подстроки.

(*) Пути в дереве суффиксов сжаты, т.е. ребро может представлять несколько символов.Вам нужно распаковать пути, чтобы получить все подстроки, т.е. обрабатывать сжатые ребра как многоузловые пути.

Answer 2

В Trie есть "конечные знаки", т. Е. Если узел является последним символом строки, он помечается как один terminal.

Так что если вам нужно распечатать все строки в Trie, вам нужно будет dfs() на этом Trie при каждом посещении узла с end sign (что означает, что это терминал), вы знаете, это последний символ какой-либо строки, поэтому напечатайте его.

Answer 3

Обратите внимание, что каждая подстрока myString имеет длину от 0 до strlen(myString). Так что просто переберите все возможные длины и все возможные начальные позиции подстроки.