левый-правый радикс

Question

Сортировка по Radix сортирует числа, начиная со значимой цифры аренды до самой значимой цифры.У меня есть следующий сценарий:

Мой алфавит - это английский алфавит, и поэтому мои "цифры" - это строки на английском языке.Символы этих строк раскрываются по одному слева направо.Таким образом, наиболее значимая цифра для всех строк раскрывается первой и так далее.На любом этапе у меня будет набор из k символов длинных строк, которые отсортированы.На данный момент еще один символ раскрывается для каждой строки.И я хочу отсортировать новый набор строк.Как мне сделать это эффективно, не начиная с нуля?

Например, если у меня был следующий отсортированный набор {for, sta, sto, sto}

И после еще одного символа каждыйраскрыто, набор: {форма, перед, звезда, остановка, остановка}

Новый отсортированный набор должен быть {перед, форма, звезда, остановка, остановка}

Я надеюсьсложность O (n) после добавления каждого нового символа, где n - размер набора.

Answer 1

Если вы хотите сделать это в O (n), вы должны каким-то образом отслеживать «группы»:

for, for | sta | sto, sto

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

Хранение групп может быть сделано различными способами. На первый взгляд, я бы порекомендовал запоминать смещения групповых начал / концовок. Однако для этого требуется дополнительная память.

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