Архивация набора строк

109

28 октября 2021, 08:40

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

Например, для таких строк

"I'm Jack"
"I'm Josh"

необходимо вернуть

"I'm Ja"
"I'm Jo"

А для следующих строк

"I'm Jack"
"I'm Josh"
"Hello"
"Hell"
"Unique"

необходимо вернуть

"I'm Ja"
"I'm Jo"
"Hello"
"Hell"
"U"

Вопрос скорее по алгоритму, но если есть удобные функции для этого в C++ или Python, то тоже было бы круто их узнать.

Answer 1

Идём по каждой строке с её начала и добавляем в std::set сначала первый символ, потом первые 2 и так далее. В конце если размер сета равен кол-ву строк, то всё. Иначе надо удалить те строки, которые лексикографически меньше других (поэтому в сете будут расположены строго раньше) и при этом не встречаются в исходном наборе строк, а также те строки, которые включают в себя другие (в сете строго после искомых строк расположены) и не встречаются в исходном наборе строк. Сам исходный набор строк тоже будет расположен в этом сете, так что это всё будет достаточно быстро.

Answer 2

Построить trie (бор), вывести подстроки такие, что конечный элемент является терминальным, или за ним идёт только один терминальный (далее нет разветвлений). Вероятно, для этого придётся хранить дополнительный признак в узлах trie