Довести строку до палиндрома , возможно, есть спец. алгоритм для этого

[FasterHarder]

Всем хай! Сразу переходим к делу, важному делу!

Задана строка.
Есть требования (я их сам дописал, чтобы недокопывались до постановки):
- входить в строку могут русские (большие и малые) буквы, знаки препинания, цифры, пробел.
- ввод происходит с клавиатуры и заканчивается нажатием ENTER
- предельная длина строки 300 символов (если кому-то важно, можете поставить 3000 или 3млрд символов)

Необходимо:
1. Получить выходную строку, состоящую из МИНИМАЛЬНОГО количества символов. Символы этой выходной строки обладают таким свойством, что если их добавить в нужные позиции стартовой строки, то исходная строка превращается в палиндром (напомню, что палиндром - текст, читающийся одинаково в обоих направлениях, например, "казак"). Символы в выходной строке могут идти в любом порядке. Вывести выходную строку на экран.

2. Получить искомый палиндром и вывести его на экран.
---------------------------------------------------------------------------------
Внимательно, пример:
исходная_строка = "оза УпаланлпУ аора"
выходная строка = "рааза" (прим. не будет ошибкой, если она будет такой ("азара") или такой ("зааар") или ...тут вариантов может быть вроде по формуле перестановок с повторениями, в данном случае = 5! / (1! * 1! * 3!) = 5!/3! = 20, может я прогнал тут чушь )).
искомый_палиндром = "ароза УпаланалапУ азора"
---------------------------------------------------------------------------------

Немного подумав, я осознал, что ни на 1% процент не выкупая эту задачу. Это нужно на рекурсии или дерево строить. а может графы, а может еще что-то. 0 идей, вообще! Была сначала идея двигаться по входной строке с разных концов (от концов к центру), но там куча проблем, что проверять, с чем проверять и пр. пр. Не знаю, короче, как это решается.

Если есть здравые мысли, то поделитесь

ЗЫ: кому важно, это НЕ ПРОМЫШЛЕННАЯ задача, а из категории "Олимпиадная", а это означает, что есть еще автоматом требования эффективности (мин. памяти + макс.быстродействие, т е мин. проверок, циклов и пр.)

Добавлено 26.06.20, 07:21
ааааа, тут, наверное, на сортировку с подсчетом...

[Black_Dragon]

Исходная строка: аааббб
Что должно получиться?

[FasterHarder]

я понял, ты клонишь к тому, что палиндромов может быть несколько:
- бббаааббб
- ааабббааа

вроде тут их только два (с минимальным кол-вом дополнений, а так бесконечное множество, разумеется)
не знаю, для упрощения, наверное ЛЮБОЙ палиндром сойдет (хотя бы этот вариант сделать)
если не упрощать, а со всеми выкладками, то ВСЕ возможные палиндромы

ЗЫ: да, хорошее замечание, я об этом чет сразу не подумал!

[Black_Dragon]

Идет с обоих концов.
Если одинаковые, идем дальше.
Если нет, то смотрим следующее, чтоб понять, в каком месте вставлять, если опять разные, то просто принимаем какое-нибудь "правило", например, символ, который со стороны начала фиксируется.

Вообщем цели или первый построенный по личным правилам или все (наверно проще на прологе).

[MBo]

Динамическое программирование. Создаём таблицу размером NxN
В ячейке A[l, r] хранится количество вставок, необходимых для создания палиндрома из подстроки l..r.

Если S[l] = S[r], то A[l, r] = A[l+1, r-1]

иначе A[l, r] есть минимум из обрезков на один символ справа и слева.

A[l, r] =min(A[l+1, r], A[l, r-1])

При выборе минимума можно запомнить символ, который будет вставлен - он понадобится для " Получить выходную строку"

Сообщение отредактировано: MBo - 26.06.20, 15:28

[amk]

Расстояние Левенштейна между строкой и её зеркальным отражением.
Символы, "уникальные" для отражения и будут необходимыми символами для вставки.