Палиндром

[Carbon]

Дано число 1<=N<=14. Затем следуют N строк, состоящие из малых латинских букв. Их от 1 до 30. Найти минимальный палиндром, содержащий все эти строки в качестве подстрок.

[SuperVisor]

Возможно, не понял задачу, но предложу решение: объявляем множество типа char, каждую новую строку посимвольно проверяем на содержание во множестве. Да - добавляем, нет - берем следующий символ.

[Virtson]

напомню, что палиндром это строка, для которой выполняется :
S[i]=S[Length-i+1],
для i от 1 до Length div 2

[Carbon]

SuperVisor, не это чё-то не туда понесло.

[rpy3uH]

полиндром - это такое слово которое в обратном порядке читается так же как в нормальном
например:
"абба", "12321" , "qwerewq" - это полиндромы
функция которая говорит полиндром ли строка:

function IsPolindrom(value:string):boolean;
var
  tmpstr:string;
  i:integer;
begin
  tmpstr:='';
  for i:=length(value) downto 1 do
   tmpstr:=tmpstr+value[i];
  Result:=tmpstr = value;
end;

пример

procedure TForm1.Button1Click(Sender: TObject);
begin
  if IsPolindrom('арозаупаланалапуазора') then ShowMessage('полиндром')
                                          else ShowMessage('не полиндром');

end;

[SuperVisor]

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

SuperVisor, не это чё-то не туда понесло.

Я потому сразу и оговорился, что мог не понять условие задачи.
В таком случае нужно начинать с наибольшей строки и искать в ней искомые подстроки. После, если в наибольшей строке не найдены все искомые строки путем сложения попытаться вывести остальные. Когда результат достигнут мы получим строку с наименьшим возможным количеством символов. После стоит попытататься найти гепотетическую середину палиндрома и от нее достроить палиндром.

[Virtson]

function IsPolindrom2(value:string):boolean;
var
  i, L, n: integer;
begin
  L:=  length(value);
  n:= L div 2;
  Result := false;
  for i:= 1 to n
    if value[i]<>value[L - i + 1] then exit;

  Result:= true;
end;

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

Найти минимальный палиндром, содержащий все
эти строки в качестве подстрок.

1. найти минимальную строку, содержашую все заданные
2. проверить не полиндром ли строка.
3. иначе нужно расширять с 2 строн. (слева и справа)
найти сначала наилучший 'центр', чтобы количество добавляемых символов было миниальным
[если наилучего нет, можно весь хвост с одной стороны добавлять]

P.S. надеюсь кто-нить понял мою мысль, особенно Carbon

Virtson, ну ты-то чему молодежь учишь? Есть кнопка "Правка".

[mihali4]

надеюсь кто-нить понял мою мысль

Мысль понятна, только у меня сомнения по поводу приведенного алгоритма.
Это потому, что мне показалось, что в задаче имеется в виду палиндром, в который любая исходная строка может входить не более одного раза.

[Carbon]

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

Это потому, что мне показалось, что в задаче имеется в виду палиндром, в который любая исходная строка может входить не более одного раза.

Не обязательно не более 1 раза. Дело в том, что слова могут пересекать центр или находиться в разных половинах. Тогда не получится формировать сначала половину, а затем зеркально её отображать.

[Virtson]

SuperVisor:
мой первый пост - ответ на алгоритм rpy3uH и никак не связан со вторым.

затем мне пришла мысль, и я написал алгоритм.