Задача про палиндром...

[isst]

Хочу предложить вам вот такую задачку:
Дана строка, в которую входят только строчные латинские буквы (то бишь слово маленькими буквами). Нужно определить, какое наименьшее число букв нужно дописать в конец слова, чтобы оно стало палиндромом. Вот.

[Poma][a]

Я бы бахнул бинарный поиск по длине самого палиндрома.. Получил бы O(nlogn)

[isst]

О-о, Рома, привет! Хорошо, учту твое предложение. Просто хотел посмотреть, кто как предложит решить, лично мой код таков, как вам?

function IsPalindrome(s:StRing):bOOlean;
 
var i, len:IntegeR;
    flag:bOOlean;
   
begin
  len:= Length(s);
  flag:= True;
  for i:= 1 to len div 2 do
  begin
    if (s[i] <> s[len - i + 1]) then
    begin
      flag:= False;
      break;
    end;
  end;
  IsPalindrome:= flag;
end;

var s, buf:String;
    l, k:LongInt;
    
begin
  readln(s);
  if IsPalindrome(s) then writeln(0)
  else
  begin
    for l:= 1 to Length(s) do
    begin
      buf:= s;
      for k:= l downto 1 do buf:= buf + buf[k];
      if IsPalindrome(buf) then break;
    end;
    writeln(l);
  end;
end.

Принимаются замечания и предложения.

[Poma][a]

В худшем случае ты получишь квадрат.. вот..
А еще не используй l, если бы не подсветка я бы с ума сошел

[isst]

Сообщение от Poma][a

В худшем случае ты получишь квадрат.. вот..
А еще не используй l, если бы не подсветка я бы с ума сошел

Какой квадрат? Ты о чем?

А насчет 'l' - это моя заветная буква...

[Poma][a]

Сложность квадратичная

[isst]

Сообщение от Poma][a

Сложность квадратичная

А-а, понял.

[FPaul]

Я недавно на другом форуме решал именно такую задачу (там ТС ничего не захотел делать сам и я своё решение не выкладывал).
Сначала я решил почти также как isst

{
Даны натуральное число N и символы S[1],...,S[n].
Преобразовать последовательность S[1],...,S[n], добавив к ней наименьшее
число символов S[n+1],...,S[m] так, чтобы последовательность S[1],...,S[m]
стала палиндромом: S[1]=S[m],S[2]=S[m-1] и т.д.
http://forum.pascalnet.ru/index.php?showtopic=30171&hl=
}

program algo002;

var
  sx:   string;
  n:    integer;
  s:    string;
  i, j: integer;
  IsPalindrom: boolean;
begin
  sx := '1234566';

  s := sx;
  n := length(s);
  IsPalindrom := False;
  i := 1;
  while i < n do
  begin
    if s[n] = s[i] then
    begin
      IsPalindrom := True;
      j := i;
      while j < n + i - j do
      begin
        if s[j] <> s[n + i - j] then
        begin
          IsPalindrom := False;
          break;
        end;
        Inc(j);
      end;
    end;
    if IsPalindrom then
      break;
    Inc(i);
  end;
  for j := i - 1 downto 1 do
    s := s + s[j];
  writeln(s);
end.

Но чуть попозже на другом форуме увидел ссылку на алгоритм (не на решение). Это алгоритм Манакера. Я воспользовался описанием алгоритма на e-maxx.ru. Но, как стало ясно из коменариев на этой странице, в реализациях кода закралась ошибка (приведены примеры). Также приведены исправления.
Перевёл код с С на Pascal и на примере с тимуса (задача 1297 с другим условием, но тоже с палиндромами) увидел ускорение работы (я не олимпиец и рейтинг пофиг):
naive 0,468-0,484 с при 374 КБ
manacher 0,015 с при 102 КБ
Сразу скажу - код получается больше. Но это как "золотое правило физики" - меньше силы, но путь длинней и наоборот.
Так, что рекомендую познакомится с алгоритмом Манакера.
----------------
PS Sorry за поток сознания. Надеюсь, что хоть чуть-чуть виден посыл - МАНАКЕР.

[rrrFer]

Интересная задача, спасибо.

[Poma][a]

Эм.. Дык это же не та задача, не?

P.S. Но все равно спасибо! У меня на acmp давно валялась задачка несделанная.. а там именно Вашим Манакером и решается