Программа, находящая в строке подпалиндром максимальной длины

Категория: Delphi/Pascal
2011-09-01 22:34:05

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

code: #pascal
  1. const N=100;
  2.       M=(N*(N+1)) div 2;
  3.  
  4. type Pair=record
  5.        left,right,prev,count:integer;
  6.      end;
  7.  
  8. var inp,outp:text;
  9.     line,result:string;
  10.     index:integer;
  11.     list:array [1..M] of Pair;
  12.  
  13.  
  14. procedure Find;
  15. var i,j,k,len,item:integer;
  16. begin
  17.   len:=length(line);
  18.   item:=1;
  19.   for i:=1 to len do
  20.     for j:=len downto i do
  21.       if line[i]=line[j] then
  22.       begin
  23.         list[item].left:=i;
  24.         list[item].right:=j;
  25.         list[item].prev:=0;
  26.         list[item].count:=0;
  27.         for k:=1 to item-1 do
  28.         begin
  29.           if (list[k].right>list[item].right) and
  30.              (list[k].left<list[item].left) and
  31.              (list[k].count>=list[item].count) then
  32.           begin
  33.             list[item].prev:=k;
  34.             list[item].count:=list[k].count+1;
  35.             if list[item].count>list[index].count then
  36.               index:=item
  37.           end;
  38.         end;
  39.         item:=item+1
  40.       end;
  41.   i:=index;
  42.   result:=line[list[i].left];
  43.   if list[i].right>i then
  44.     result:=result+line[list[i].left];
  45.   while i>0 do
  46.   begin
  47.     i:=list[i].prev;
  48.     if i>0 then
  49.       result:=line[list[i].left]+result+line[list[i].left];
  50.   end
  51. end;
  52.  
  53. begin
  54.   assign(inp,'input.txt');
  55.   reset(inp);
  56.   readln(inp,line);
  57.   index:=1;
  58.   Find;
  59.   close(inp);
  60.   assign(outp,'output.txt');
  61.   rewrite(outp);
  62.   writeln(outp,length(result));
  63.   writeln(outp,result);
  64.   close(outp);
  65. end.
Поделиться:

Похожие статьи:

теги: консольное приложение, студенты, работа со строками, строки, палиндромом