Алгоритм для поиска всех подстрок из заданного массива строки

Question

Мне нужно найти все подстроки из заданного массива строк и сгруппировать их.

Дополнительного условие:

Если строка S1 содержит строку S2, S1 содержит S3, S2 содержит S4 - все они должны быть в одной группы.

Пример:

Учитывая массив: Здравствуйте, Привет Джон, Привет, Привет Боб, Ад, Привет всем

Результат вывода:

Группа 1: Здравствуйте, Hello John, Hell

Группа 2: Привет, Привет, Боб, Привет всем

Answer 1

• Построить trie на массив строк
• Для каждой записи массива, ходить и синтаксического дерева, если текущий узел отмечает слово, распечатать его (в той же группе, что и текущей строки). Сделайте некоторые бухгалтерии, чтобы избежать многократного тиражирования одного и того же слова.

Временная сложность для создания шины O(|w1| + ... + |wn|), где |wi| длина строки wi; поэтому он является линейным в сумме длин строк. Сложность пространства ограничена одним и тем же выражением, но намного ниже, когда существует множество общих префиксов (что и происходит на практике).

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

Вот структура, чтобы вы начали:

typedef struct node_t_ node_t; 
struct node_t_ { 
    node_t c *children[ALPHABET_SIZE]; 
    char kIsLeaf; // set to 1 if represents a word 
    char ch; // character stored in the leaf (redundant) 
} 

Установка проста. Вы начинаете с не-NULL root, который сохраняет нулевой символ (представляет пустую строку).

Вставка:

void insert(const char* str) { 
    node_t* current = root; 
    while (*str != '\0') { 
     if (current->children[*str] == NULL) { 
      create new node; 
     } 
     current = current->children[*str++]; 
    } 
    current->kIsLeaf = 1; 
} 

Остальные процедуры очень похожи. Trie - очень элегантная, простая в использовании и удобная в использовании структура данных.