структура данных три и печать всех подстрок

Question

Мне нужно напечатать все уникальные подстроки.Поэтому я создаю trie, но не могу понять, как я могу распечатать все подстроки.Например, если введено значение aab и aac, то я ожидаю, что оно напечатает "a", "aa", "aab", "aac", "ab", "ac", "b", "c".

Что по сути мне нужно, чтобы найти способ получить уникальные подстроки из набора строк.Я думаю, trie - это хороший способ, поскольку для создания trie потребуется O(n)

. Ниже приведен мой код для построения дерева.

#include <string>
#include <iostream>
#include <vector>

struct trie_node {
    trie_node *(next[26]);

    trie_node() {
        for ( int i = 0; i < 26; ++i) {
            next[i] = (trie_node*)0;
        }
    }
};

trie_node *root;
char cur_substring[2000];
void build_trie(std::string& input) {
    trie_node *ptrie = root;
    for ( std::string::iterator it = input.begin(); it != input.end(); ++it) {
        int i = *it - 'a';
        if (ptrie->next[i] == (trie_node*)0)
            ptrie->next[i] = new trie_node;
        ptrie = ptrie->next[i];
    }
}

void print_sub_strings(trie_node *p_trie, int pos) {
    for (int i = 0; i < 26; i++) {
        if (p_trie->next[i] != (trie_node*)0) {
            cur_substring[pos] = i + 'a';
            print_sub_strings(p_trie->next[i], pos + 1 );
        }
    }
}

ОБНОВЛЕНИЕ 1

На основании полученных данных я переписал свой код, но, похоже, он также не работает.*

Вывод

a
aa
aab
aabc
aab
aabc
ab
abc
Press any key to continue . . .

Answer 1

Trie хранит разные строки, но не заботится об их подстроках, которые не начинаются с первой буквы. Каждая строка, хранящаяся в Trie, начинается от корневого до некорневого узла. Вы можете попытаться подобрать подстроку от некорневого узла к другому некорневому узлу, но это не может гарантировать уникальность подстроки.

Например, строка " abab " сохраняется. Вы можете получить уникальные строки a , ab , aba , abab от корневого до некорневого узла. Если вы попытаетесь подобрать строку, начинающуюся с некорневых узлов, вы получите

• a b ab
• а ба б
• a bab
• ab a b
• ab ab
• аба б

, где a , ab и b уже существуют. Вы можете попытаться сохранить все концы подстрок в последней букве, чтобы избежать этого. Например, когда появляется новая строка " abcdab ", вам необходимо сохранить " abcdab ", " bcdab ", " cdab"," dab"," ab"и" b"в Трие. В любом случае, это делает сложность времени O (n ^ 2), а не O (n).

Answer 2

Если вы хотите получить все подстроки строки (включая те, которые не начинаются с первой буквы), вы должны хранить суффиксы строки в дереве.

т.е. что вы делаете, вы сохраняете полную строку, затем сохраняете строку без первой буквы, затем без второй буквы и т. д. Таким образом, трия правильно обрабатывает удаление повторяющихся подстрок, и когда вы обойдете ее, вы получите все правильные подстроки , Однако обратите внимание, что это не O (n), что, как правильно отметили другие, является невозможной оценкой для такого рода проблем.

Обычный вариант использования для такого рода структуры данных, однако, это быстрый поиск подстрок. Если вы сохраняете при каждом выходе позицию, в которой вы начали суффиксы (их может быть несколько), вы можете легко найти все вхождения любой подстроки в произвольно длинной подстроке. Именно здесь попытки играют свою роль в поисковых задачах, таких как полнотекстовый поиск.

EDIT

После вашего обновления вы добавляете локальную префиксную переменную в цикле, поэтому, когда вы исследуете следующий дочерний элемент в цикле, он будет иметь неправильное значение. Дополнительные значения, которых не должно быть в вашем примере, вызваны этим. Вы должны создать новую префиксную переменную в каждой итерации и передать ее. Вы можете найти исправленный код с дополнительными выходами отладки здесь .

Answer 3

Что ж, если вы правильно построили структуру Trie с учетом каждой строки, то при обходе Trie вы получите все возможные подстроки исходных строк. Дубликаты обрабатываются автоматически благодаря структуре попыток.