Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.06.2007, 10:54   #11
katya_milovanova
 
Регистрация: 15.06.2007
Сообщений: 4
По умолчанию

Цитата:
Сообщение от 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.
Спасибо болььшое
katya_milovanova вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц