Палиндром???

[viva2222]

Задачка звучит так. Дано какое-то слово, состоящее только из латинских букв, не более 20 символов. При вычеркивании каких-нибудь символов из него, образуется палиндром. Нужно посчитать количество таких вычеркиваний в этом слове, если учитывать, что порядок вычеркивания это одно и тоже.
Например: ВАОВАВ
Ответ: 22

[viva2222]

Ну народ, плиз помогите(((

[LeBron]

Динамика на подстроках. Хранить количество способов для подстроки от
х до y. База динамики - 1 для одной буквы (тоесть с 1 буквы можно сделать палиндром ровно 1 способом) и для любой пары одинаковых символов.
Дальше идем расширяющимся обходом, и к каждому варианту пытаемся "приписать" слева и справа по одинаковой букве, тоесть ищем для каждой подстроки, для которой ответ больше 0 те подстроки, для которых она увеличивает ответ, и прибавляем к ответам для этих подстрок значение для нашей строки.
Ответом в конце будет сумма всех значений таблицы динамики.
-=-=-=-=-=-
Это если нормальное решение, которое работает и для 30, и даже для 40-50 символов (асимптотика N^4) в пределах секунды. Если делать "влоб", то полный перебор - перебираем все битовые маски и смотрим, дает ли нам определенная маска палиндром. Сложность N*2^N, тоесть для 20 мы имеем условно 20 миллионов операций, что не очень много, а уже для 30 будет более 30 миллиардов, что занимает несколько минут.

[viva2222]

Простым перебором мне не надо, у мя типа динамическое программирование. А вот твой метод я что-то не очень понял. Не разобрался!!!

[LeBron]

У мя типа тоже.

Вообще хоть немного в динамике разбираетесь? Если да, то сдесь ничего сложного. Сначала заполняем базу динамики. Потом перебираем все подстроки длины 1 и пробуем приписать к ним слева и справа по одинаковой букве (точнее не приписать, а найти в строке), для позиций тех букв, которые мы приписали - увеличиваем ответ на ответ для текущей подстроки (мы можем приписать эти 2 буквы к любому из "ответов" для даной подстроки). Потом длины 2, длины 3, длины 4...

Если быть более точным, то в позиции динамики (х,у) мы храним количество способов вычеркнуть произвольное (возможно, пустое) множество символов из подстроки, которая начинается на позиции х и заканчивается на позиции у, не вычеркивая крайних слева и справа, так, чтоб образовался палиндром.

[viva2222]

ммм.... кажется хоть чуть-чуть понял... хотя не понимаю, как заполнять динамику (я так понял вы так назвали матрицу, двумерный массив)...

[LeBron]

Сообщение от viva2222

ммм.... кажется хоть чуть-чуть понял... хотя не понимаю, как заполнять динамику (я так понял вы так назвали матрицу, двумерный массив)...

Смотрите, ведь что от нас требуют? Выбрать некоторые буквы, так чтобы они давали палиндром. Если мы взяли слово, и оно является палиндромом, то к нему можно приписать одинаковые буквы справа и слева, так, что образуетя новый палиндром, и это справедливо всегда (хочу заметить, что случаи, кода есть подстрока типа "ааа", и можно получить палиндром добавлением одной буквы - "аааа", будут учтены - этот пример можно получить из "а+аа+а", мы отдельно рассмотрим четную и нечетную длину). Так вот, для нас не важно, что между крайними буквами (к которым приписываем), важно только, где эти буквы, и сколько всего вариантов есть выбрать эти самые "буквы между ними".

Мы можем взять любой из этих вариантов (пример: если есть "авббга", то за нашим определением можно взять "аа","ава", "аба", "аба", "ага", "абба"), приписать к нему по одинаковой букве с каждой стороны - и получим новый палиндром.
Поэтому мы для каждой подстроки перебираем все комбинации букв "слева-справа", тоесть 1 буква левее этой подстроки и 1 правее, если эти буквы одинаковы - то мы можем для подстроки, ограниченой уже этими буквами, увеличить ответ на ответ для текущей подстроки (ко всем ответам текущей подстроки приписать эти 2 буквы - и получим как раз такое число "дополнительных" ответов для той подстроки).
Как двигаться по подстроках одинаковой длины - для нас не важно. Главное - перебрать все. Важно другое - то, что надо перебирать от более коротких к более длинным подстрокам. Если делать иначе, то может быть такое, что мы, рассматривая, к примеру, подстроку из 10 символов, будем иметь для нее неверный ответ, потому что еще не посчитали какой-то из палиндромов, которые можно приплюсовать за счет более короткой подстроки - скажем, 8 символов (которую мы не рассмотрели).
Ну а если двигаться от более коротких к более длинным, то всегда будем влиять на результаты для подстрок, которые еще не рассмотрели, а не на те, которые уже прошли.