Математика: Комбинаторика и перебор.

Дана строка 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

Эта задача реализуется следующим рекурсивным алгоритмом поиска с возвращением (все слова набора A упорядочены по номерам):

а) Если строка пустая, то одна из возможных дешифровок найдена, иначе при разборе текста мы проверяем А[i] (при изменении i от 1 до n) на вхождение в начало дешифруемой в данный момент строки.

б) Если какое-то A[i] входит в строку как префикс, то запоминаем номер i этого слова, затем выделяем слово из строки, а с остатком текста производим операцию разбора по пункту а).

Если ни одно из A[i] не входит в качестве префикса в дешифруемую сейчас строку, то осуществляем возврат на пункт а), предварительно добавляя в начало строки последнее удаленное оттуда слово, и пытаемся выделить из текста слово с большим номером в A. Если возврат осуществить невозможно (т. к. мы находимся в начале исходной строки), то алгоритм заканчивает свою работу. Все возможные дешифровки найдены.

Вверх по странице, к оглавлению и навигации.