Trie структура данных

Question

Данные N строк. Каждая строка содержит только строчные буквы от a−j (оба включительно). Набор из N строк называется ХОРОШЕЕ SET, если строка не является префиксом другой строки else, это BAD SET.

Например, aab, abcde, aabcd является BAD SET, потому что это aab префикс aabcd.

Печать ХОРОШЕЕ УСТРОЙСТВО, если оно удовлетворяет требованиям проблемы. Else, print BAD SET и первая строка, для которой условие не работает.

вход Формат:
Первая строка содержит N, число строк в наборе. Затем следуют следующие N строк, где i-я строка содержит i-ю строку.

Ограничения:
1 ≤ N ≤ 105 1 ≤ Длина строки ≤60

Формат вывода:
Выходные ХОРОШО SET, если набор является действительным.
Else, output BAD SET, за которым следует первая строка, для которой условие не работает.

Может ли кто-нибудь предложить на это?

Answer 1

Построить a trie, вставляя каждую строку в trie один за другим, записывая указатели на узлы, представляющие каждую строку, вставленную в trie. После этого сканируйте указатели на узлы для всех строк. Если какой-либо из них заканчивается на внутреннем узле, то это BAD SET. в противном случае (все строки заканчиваются на разных листьях), это ХОРОШИЙ УСТАНОВ. Сложность времени и пространства как линейная, так и полная длина всех строк.