Пример: S=ABBC
A[1]=A, A[2]=AB, A[3]=BC, A[4]=BBC, A[5]=H, A[6]=B
S = A B BC
= A BBC
= AB BC
Эта задача реализуется следующим рекурсивным алгоритмом поиска с
возвращением (все слова набора A упорядочены по номерам):
а) Если строка пустая, то одна из возможных дешифровок найдена,
иначе при разборе текста мы проверяем А[i] (при изменении i от 1 до
n) на вхождение в начало дешифруемой в данный момент строки.
б) Если какое-то A[i] входит в строку как префикс, то запоминаем
номер i этого слова, затем выделяем слово из строки, а с остатком
текста производим операцию разбора по пункту а).
Если ни одно из A[i] не входит в качестве префикса в дешифруемую
сейчас строку, то осуществляем возврат на пункт а), предварительно
добавляя в начало строки последнее удаленное оттуда слово, и
пытаемся выделить из текста слово с большим номером в A. Если
возврат осуществить невозможно (т. к. мы находимся в начале исходной
строки), то алгоритм заканчивает свою работу. Все возможные
дешифровки найдены.
Назад
