|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
25.01.2015, 16:56 | #1 |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
Задача про палиндром...
Хочу предложить вам вот такую задачку:
Дана строка, в которую входят только строчные латинские буквы (то бишь слово маленькими буквами). Нужно определить, какое наименьшее число букв нужно дописать в конец слова, чтобы оно стало палиндромом. Вот. |
25.01.2015, 16:58 | #2 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Я бы бахнул бинарный поиск по длине самого палиндрома.. Получил бы O(nlogn)
|
25.01.2015, 17:13 | #3 |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
О-о, Рома, привет! Хорошо, учту твое предложение. Просто хотел посмотреть, кто как предложит решить, лично мой код таков, как вам?
Код:
|
25.01.2015, 17:16 | #4 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
В худшем случае ты получишь квадрат.. вот..
А еще не используй l, если бы не подсветка я бы с ума сошел |
25.01.2015, 17:22 | #5 |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
|
25.01.2015, 17:26 | #6 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Сложность квадратичная
|
25.01.2015, 18:17 | #7 |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
|
25.01.2015, 23:21 | #8 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Я недавно на другом форуме решал именно такую задачу (там ТС ничего не захотел делать сам и я своё решение не выкладывал).
Сначала я решил почти также как isst Код:
Перевёл код с С на Pascal и на примере с тимуса (задача 1297 с другим условием, но тоже с палиндромами) увидел ускорение работы (я не олимпиец и рейтинг пофиг): naive 0,468-0,484 с при 374 КБ manacher 0,015 с при 102 КБ Сразу скажу - код получается больше. Но это как "золотое правило физики" - меньше силы, но путь длинней и наоборот. Так, что рекомендую познакомится с алгоритмом Манакера. ---------------- PS Sorry за поток сознания. Надеюсь, что хоть чуть-чуть виден посыл - МАНАКЕР. |
26.01.2015, 06:07 | #9 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Интересная задача, спасибо.
|
26.01.2015, 08:21 | #10 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Эм.. Дык это же не та задача, не?
P.S. Но все равно спасибо! У меня на acmp давно валялась задачка несделанная.. а там именно Вашим Манакером и решается |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача про окружности | makskovalko | Помощь студентам | 2 | 01.12.2013 23:49 |
Задача на палиндром | Me gusta | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 27.03.2013 19:17 |
задача про улитку | leo-leo | C++ Builder | 6 | 08.07.2012 17:35 |
Задача про матрицы | Dzenin | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 24.02.2011 16:55 |
проверьте программу про палиндром | Nice rabbit | Помощь студентам | 8 | 09.03.2010 16:35 |