Задача 4.2.
Дана строка S и набор A слов А[1], ..., A[k]. Разбить строку S на слова набора всеми возможными способами.
Пример: 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
|
Решение задачи 4.2.
Эта задача реализуется следующим рекурсивным алгоритмом поиска с возвращением (все слова набора A упорядочены по номерам):
а) Если строка пустая, то одна из возможных дешифровок найдена, иначе при разборе текста мы проверяем А[i] (при изменении i от 1 до n) на вхождение в начало дешифруемой в данный момент строки.
б) Если какое-то A[i] входит в строку как префикс, то запоминаем номер i этого слова, затем выделяем слово из строки, а с остатком текста производим операцию разбора по пункту а).
Если ни одно из A[i] не входит в качестве префикса в дешифруемую сейчас строку, то осуществляем возврат на пункт а), предварительно добавляя в начало строки последнее удаленное оттуда слово, и пытаемся выделить из текста слово с большим номером в A. Если возврат осуществить невозможно (т. к. мы находимся в начале исходной строки), то алгоритм заканчивает свою работу. Все возможные дешифровки найдены.
|
