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

[k1r1ch]

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.
Формат входных данных
Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.
Формат выходных данных
В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.

Вот такая задача. Я в принципе догадываюсь, что тут динамическое программирование нужно. Но вот как-то не могу программу написать . То есть как организовать массив и что в нем хранить? Я думал булевый массив 100 на 100 и там хранить, совпадают ли символы или нет... А потом использовать массив как матрицу смежности и найти наибольший путь на графе. Только как наибольший путь найти (наименьший только знаю) и вообще это решение кривовато немного наверное? Может по-другому можно? Надеюсь на помощь!

[Stilet]

Предлагаю следующее:

var s,e:string;k,i:integer;
begin
 s:='HTEOLFEOLEH';
 for i:=0 to length(s) do begin
  for k:=i+1 to length(s) do begin
   if(s[i]=s[k]) then begin e:=e+s[k]; break; end;
  end;
 end;
   write(e);
 for i:=length(e) downto 1 do begin
  write(e[i]);
 end;
readln;
end.

Смысл понятен? Я так приблизительно - тут доводочку бы насчет неповторяющихся букв сделать.

[k1r1ch]

Сейчас попытаюсь разобраться в коде, но по крайней мере вот эту строчку:
TOYUDOTTGOO он не правильно обрабатывает (пишет TOOTOOTOOT)

З.Ы.: Зачем эту тему перенесли в раздел "Помощь студентам"? Я не студент, и чем тема не устраивала в "Паскале"?

З.Ы.Ы.: Я что-то похожее пытался сделать, там оно ошибалось на тех же строках, что и тут. Так что нужно другое решение...

[LeBron]

При таких ограничениях вообще ничего не нужно, проходит тупой полный перебор. А вообще - для спортивного программирования сложно придумать более плохо влияющий на рост программиста поступок, чем спрашивание решения у других. Разве что копипаст готового кода с сети. Единственное оправдание - "за вермя, которое я потратил бы на решение этой задачи, я решу что-то другое".

[k1r1ch]

Нет, это тут такие ограничения, просто я уже много задач видел на строки, где используется динамическое программирование, и не одну не понял как решать! Понимаю, когда там "Черепашка" какая-нибудь, когда заводим массив (двумерный или одномерный) и там высчитываем количество вариантов рекурсией или итеративно. А тут как-то не понимаю, что в массив то записывать?

[LeBron]

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

Нет, это тут такие ограничения, просто я уже много задач видел на строки, где используется динамическое программирование, и не одну не понял как решать! Понимаю, когда там "Черепашка" какая-нибудь, когда заводим массив (двумерный или одномерный) и там высчитываем количество вариантов рекурсией или итеративно. А тут как-то не понимаю, что в массив то записывать?

Повторю еще раз, мне все равно, так как для меня ничего не измениться, но Вам же хуже от того, что Вы не решаете задачу сами. Если так уж хотите, то что поделать... Объясню, как решать.
Можно решать прямыми q-хэшами за NlogN. Есть как минимум 3 сравнительно простых метода решения за линейное время - формально-комплектарная "быстрая" динамика (З.Ы, не знаю, как ее гуглить, в РуНете не видел... может запрос "псевдохэш" поможет, но лучше искать в англоязычной части сети), LCA-сводка, условная Z-функция. Можете гуглить любой из них, объяснять сдесь будет слишком долго, да и при моем таланте объяснителя придеться одно и то же повторять по 3 раза разными способами. Один должен быть на Алголисте, 1 или 2 на Е-максе. Даже в Вики кажеться есть инфа.

[k1r1ch]

http://comp-science.narod.ru/WebPage/p6.htm
Вот наткнулся на решение именно этой задачи! Это какой из названных способов?

[LeBron]

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

http://comp-science.narod.ru/WebPage/p6.htm
Вот наткнулся на решение именно этой задачи! Это какой из названных способов?

Это вообще 4ый. Он имеет мало общего с первыми 3мя.