Алгоритмы на строках

Оценим сложность операций над этой структурой данных. Все операции (добавление, удаление, поиск) для данной строки длины L выполняются за время O(L), при этом памяти требуется O(S*M), где S — сумма длин всех строк, M — размер алфавита. Видно, что узкое место структуры данных в объеме используемой памяти.

Рассмотрим метод устранения этого недостатка.