Помогите!

[katya_milovanova]

Помогите пожалуйста... Осталось одну задачу сдать а я не могу ее сделать Все экзамены автоматом а зачет не могу получить...

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

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

[S.W.A.T.]

378710771 стучись

[Carbon]

Все экзамены автоматом

Задача интересная (я уже знаю как решать), сейчас только от сегодняшнего экзамена очухаюсь.

ЗЫ: На каком языке надо? (Предполагаю, Паскаль)

[AVer]

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

Задача интересная (я уже знаю как решать), сейчас только от сегодняшнего экзамена очухаюсь.

ЗЫ: На каком языке надо? (Предполагаю, Паскаль)

Большинство заданий на этм форуме (В данном разделе) даются на языке Delphi\Pascal. Если нет - указывается в задании.

[Carbon]

const N=100;
      M=(N*(N+1)) div 2;

type Pair=record
       left,right,prev,count:integer;
     end;

var inp,outp:text;
    line,result:string;
    index:integer;
    list:array [1..M] of Pair;


procedure Find;
var i,j,k,len,item:integer;
begin
  len:=length(line);
  item:=1;
  for i:=1 to len do
    for j:=len downto i do
      if line[i]=line[j] then
      begin
        list[item].left:=i;
        list[item].right:=j;
        list[item].prev:=0;
        list[item].count:=0;
        for k:=1 to item-1 do
        begin
          if (list[k].right>list[item].right) and
             (list[k].left<list[item].left) and
             (list[k].count>=list[item].count) then
          begin
            list[item].prev:=k;
            list[item].count:=list[k].count+1;
            if list[item].count>list[index].count then
              index:=item
          end;
        end;
        item:=item+1
      end;
  i:=index;
  result:=line[list[i].left];
  if list[i].right>i then
    result:=result+line[list[i].left];
  while i>0 do
  begin
    i:=list[i].prev;
    if i>0 then
      result:=line[list[i].left]+result+line[list[i].left];
  end
end;

begin
  assign(inp,'input.txt');
  reset(inp);
  readln(inp,line);
  index:=1;
  Find;
  close(inp);
  assign(outp,'output.txt');
  rewrite(outp);
  writeln(outp,length(result));
  writeln(outp,result);
  close(outp);
end.

Я думаю, пояснения не нужны. При желании можно разобраться. Метод - динамическое программирование.
Предполагается, что данные считываются из файла input.txt и записываются в output.txt, input.txt существует и непуст.

[AVer]

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

Я думаю, пояснения не нужны. При желании можно разобраться. Метод - динамическое программирование.
Предполагается, что данные считываются из файла input.txt и записываются в output.txt, input.txt существует и непуст.

Дело в том, что входные данные - строка. Выход - тоже. Конечно нет ничего страшного и все просто переписывается, но это не соответствие заданию.

[Carbon]

Дело в том, что входные данные - строка. Выход - тоже. Конечно нет ничего страшного и все просто переписывается, но это не соответствие заданию.

Там не было написано, откуда считывается и куда записывается.
Выход - не только строка, а число и строка.

[katya_milovanova]

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

Задача интересная (я уже знаю как решать), сейчас только от сегодняшнего экзамена очухаюсь.

ЗЫ: На каком языке надо? (Предполагаю, Паскаль)

Паскаль нужно...

[katya_milovanova]

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

const N=100;
      M=(N*(N+1)) div 2;
 
type Pair=record
       left,right,prev,count:integer;
     end;
 
var inp,outp:text;
    line,result:string;
    index:integer;
    list:array [1..M] of Pair;
 
 
procedure Find;
var i,j,k,len,item:integer;
begin
  len:=length(line);
  item:=1;
  for i:=1 to len do
    for j:=len downto i do
      if line[i]=line[j] then
      begin
        list[item].left:=i;
        list[item].right:=j;
        list[item].prev:=0;
        list[item].count:=0;
        for k:=1 to item-1 do
        begin
          if (list[k].right>list[item].right) and
             (list[k].left<list[item].left) and
             (list[k].count>=list[item].count) then
          begin
            list[item].prev:=k;
            list[item].count:=list[k].count+1;
            if list[item].count>list[index].count then
              index:=item
          end;
        end;
        item:=item+1
      end;
  i:=index;
  result:=line[list[i].left];
  if list[i].right>i then
    result:=result+line[list[i].left];
  while i>0 do
  begin
    i:=list[i].prev;
    if i>0 then
      result:=line[list[i].left]+result+line[list[i].left];
  end
end;
 
begin
  assign(inp,'input.txt');
  reset(inp);
  readln(inp,line);
  index:=1;
  Find;
  close(inp);
  assign(outp,'output.txt');
  rewrite(outp);
  writeln(outp,length(result));
  writeln(outp,result);
  close(outp);
end.

Я думаю, пояснения не нужны. При желании можно разобраться. Метод - динамическое программирование.
Предполагается, что данные считываются из файла input.txt и записываются в output.txt, input.txt существует и непуст.

Ничего не понятно, и действительно нужна строка.

[Carbon]

Всё по задаче. Возвращает количество символов и строку.
Если нужна консоль:

const N=100; //максимальное количество символов
      M=(N*(N+1)) div 2; //максимальное количество вариантов
                                 //расположений пары символов
 
{Структура Pair описывает расположение пары одинаковых символов:
левый, правый, индекс массива обрамляющей пары, максимальное
количество обрамляющих пар символов, включая текущую.}

type Pair=record
       left,right,prev,count:integer;
     end;
 
var
    line, //Вход
    result:string; //Выход
    index:integer; //Индекс массива, содержащего максимальное
                       //количество пар
    list:array [1..M] of Pair; //Список пар
 
 
procedure Find;
var i,j,k,len,item:integer;
begin
  len:=length(line); //Длина строки
  item:=1;             //Текущий индекс в списке
  for i:=1 to len do  //Пробегаемся по строке, определяя пары
    for j:=len downto i do
      if line[i]=line[j] then //Если найдена
      begin
        //Записываем её данные в массив
        list[item].left:=i;
        list[item].right:=j;
        list[item].prev:=0;
        list[item].count:=0;
        //Пробегаемся по списку пар
        for k:=1 to item-1 do
        begin
          //Если нашли обрамляющую пару и количество пар больше
          //максимального для данной пары, сохраняем ссылку на пару
          if (list[k].right>list[item].right) and
             (list[k].left<list[item].left) and
             (list[k].count>=list[item].count) then
          begin
            list[item].prev:=k; //Сохраняем ссылку
            list[item].count:=list[k].count+1; //Сохраняем количество
            //Если количество больше всех остальных
            if list[item].count>list[index].count then
              index:=item
          end;
        end;
        //Увеличиваем индекс для записи следующей пары
        item:=item+1
      end;
  //После того, как найден индекс пары с максимальным количеством
  //обрамляющих пар, проходим по цепочке через индекс prev
  i:=index;
  result:=line[list[i].left]; //Формируем строку
  if list[i].right>list[i].left then      //Если это не одиночный символ,
                                             //дублируем его
    result:=result+line[list[i].left];
  while i>0 do //Пока ссылка указывает на элемент массива
  begin
    i:=list[i].prev; //Индекс обрамляющей пары
    if i>0 then //Если он не 0, добавляем пару к результату
      result:=line[list[i].left]+result+line[list[i].left];
  end
end;
 
begin
  readln(line);          
  index:=1;
  Find;
  writeln(length(result));
  writeln(result);
end.