Структура trie для слова с подсловами

Question

Какова будет структура trie для слов с подсловами типа «icecream» (содержит «i», «ice», «cream», «icecream»); «бизнесмен» (содержит «автобус», «есть», «бизнес», «человек», «бизнесмен»).

Я знаю, как это будет для тех, у кого нет подслов вроде «inn», но я смущен для вышеуказанных слов.

Заранее спасибо.

Answer 1

Вы можете просто иметь логическое «isTerminal» в своем trie-узле, чтобы указать, заканчивается ли слово на этом узле. Итак, все слова «автобус», «бизнес» и «бизнесмен» начинаются с узла «b» и проходят по одному и тому же пути. Узлы в 's' для 'bus', 's' для 'business' и 'n' для 'business' будут иметь isTerminal = true.

Хотя «человек» содержится в «предпринимателе», его следует рассматривать как слово, начинающееся с дочернего узла «m» от корня и по отдельному пути.

Поэтому все слова начинаются строго из верхних буквенных узлов (дети от корня) и заканчиваются на разных уровнях, обозначаемых логическим значением isTerminal = true.