алгоритм синтаксического анализа строки со словарем.

Учитывая

• словарь, полный слов {in, july, den, dentist, best, ...} с некоторым C ++ API для доступа к нему: boolean findWord (строковое слово) или строка getNextWord (void) для итерации по нему,

• некоторая входная строка без пробела, например: bestdentistinjuly ...

Результат

• лучший стоматолог июля - это ... (в основном разделите непространственную строку пробелом с учетом словаря)

Какой алгоритм будет лучшим для ее решения?

Тонкий, но важный вопрос: есть ли какой-нибудь необычный способ решить недостижимую тупиковую проблему . Например, den и дантист - оба подходящие слова для анализа оставшейся части строки, одно из них может быть просто тупиком.

Мне это кажется жадным проблема или что-то, что можно решить с помощью динамического программирования ..