1 Тема від bogdandacik

  • bogdandacik
  • Користувач
  • Поза форумом
  • Дата реєстрації: 23.11.2018
  • Повідомлень: 27
    • Репутація: 1

Тема: Допоможіть оптимізувати код знаходження найдовшого підрядка паліндрома

Зенику задано рядок S, який складається з N англійських літер. Потрібно допомогти йому порахувати довжину найбільшого підрядка, який є паліндромом.
  Вхідні дані:
В першому рядку задане одне ціле число N - розмір рядка.
В другому задано рядок S який складається з N малих англійських літер.
Вихідні дані: в єдиному рядку вивести довжину найбільшого підрядка S, який є паліндромом.
    Обмеження: 1<=N<=7000
  Пробний тест:
   N=6
    S=banana
   Результат: 5
Я написав код який на алготестері проходить лише для 10 тестів. Розумію, що при великих кількостях символів він є неефективним. Чув що можна оптимізувати використовуючи алгоритм Манакера про не розумію як це зробити. Ось мій код:

2 Відповідь від /KIT\

  • /KIT\
  • Меломан
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 25.09.2015
  • Повідомлень: 1 397
    • Репутація: 804

Re: Допоможіть оптимізувати код знаходження найдовшого підрядка паліндрома

Де код?

Подякували: koala, Chemist-i2

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 607
    • Репутація: 13315

Re: Допоможіть оптимізувати код знаходження найдовшого підрядка паліндрома

Коли додаєте файл, треба натискати "add file".
Але якщо там рівно один файл з кодом, викладайте код прямо в тексті, у тегу code (кнопка <>)

koala вебсайт

4 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Re: Допоможіть оптимізувати код знаходження найдовшого підрядка паліндрома

Оо, ще один чувак з Львівських Універів

5 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 725
    • Репутація: 717

Re: Допоможіть оптимізувати код знаходження найдовшого підрядка паліндрома

Якщо по темі, то мабуть все ви написали простим лінійним (або щось не дуже заморочливе) алгоритмом. 10 тестів пройшло, далі - ноу, бо більші вхідні дані.

На хабрі є повний псевдокод, гуглити: "динамічне програмування, паліндром". Я зміг розібратись колись