Рекурсивная сборка палиндрома из подстрок

Rust Сложный functions

Задача «Рекурсивная сборка палиндрома из подстрок»

Дана строка S, состоящая из строчных латинских букв. Необходимо рекурсивно (с использованием функции) разбить исходную строку на минимальное количество палиндромных подстрок (каждая подстрока должна быть палиндромом) и вывести их через пробел. Если разбиение невозможно (например, строка пустая), вывести "NO". Ограничения: длина S от 1 до 1000 символов. Гарантируется, что ответ существует.

Формат ввода

Одна строка S (1 ≤ |S| ≤ 1000).

Формат вывода

Строка, содержащая подстроки-палиндромы, разделённые пробелом. Если входная строка пустая, вывести "NO".

Примеры

Пример 1

ВВОД

racecar

ВЫВОД

racecar

Пример 2

ВВОД

aab

ВЫВОД

aa b

main.rs