В общем, с least unique string я решил забить, ибо ну его нафиг. А вот по поводу префиксного дерева, я сделал следующую штуку:

Делим путь на сегменты. Сегмент - это кусочек между слэшами. Каждый сегмент может быть как статическим, так и динамическим. Если статический - мы берём из хэшмапы следующий узел, и идём дальше. А вот если динамический - кладём этот самый сегмент в контекст, и точно также идём дальше

получилось не слишком медленно, что-то около 390нс в самом длинном шаблоне, представленным у меня в тестах. Производительность всего роутера с фоллбеком к префиксному дереву я пока не мерял