Эффективный способ токенизации строки - C

Я пытаюсь токенизировать строку. У меня есть таблица доступных токенов, заказанная в виде дерева . Каждый токен знает, что у него есть дети. Простая таблица токенов будет выглядеть так:

pattern    value         has_children
--------   ------        --------
s          s-val         1
stack      stack-val     0
over       over-val      1
overflow   overflow-val  0

В этой таблице стек является дочерним по отношению к s , а переполнение является дочерним по отношению к над . На практике в этой таблице будет упорядочено более 5000 записей.

Теперь, учитывая строку stackover , она должна вывести stack-valover-val . Алгоритм жадный и всегда будет пытаться найти самое длинное совпадение.

Для этого я начну читать каждый символ из ввода, искать совпадение, если совпадение найдено и у токена есть дочерние элементы, снова искать совпадение, включая следующий символ. Делайте это, пока не найдем самое длинное совпадение. Если совпадений не найдено, попробуйте сопоставить, включив следующий символ, пока мы не дойдем до конца строки или не добьемся успешного совпадения.

Если мы достигли конца строки без совпадения, выведите символ ? и удалите первый символ из ввода. Повторите весь процесс с оставшимися символами.

Этот алгоритм работает, но возврат и повторение всех возможных комбинаций ввода делает его медленным и сложным.

Интересно, есть ли лучший способ решить эту проблему? Любая помощь будет оценена.