Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Подпалиндромы требуется найти чилсо
Ответ
 
Опции темы Опции просмотра
  (#31 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 17.01.2009, 22:58

Ну в общем ты прав... А надо все...
Ответить с цитированием
  (#32 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 18.01.2009, 13:50

Я понял!!! Я сделал за O(n lg n)!
При нахождении двух (или одной) одинаковых букв алгоритмом Кошмара мы двоичным поиском ищем границы!!!!!!!!!!!!!
Блин, как я сразу не догадался... Уже скормил квадрат...
Ответить с цитированием
  (#33 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 18.01.2009, 14:51

wvbcsdabadrcbg

находим aba, затем двоичным поиском находим границу b...b, итого нашли подпалиндром
bcsdabadrcb
хотя он таковым не является, потому что s не равно r.
А если проверять все буквы подряд - то будет опять то, с чего мы начинали.
Ответить с цитированием
  (#34 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 18.01.2009, 16:15

А... ну в общем - да, я поторопился.
Ответить с цитированием
  (#35 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 18.01.2009, 17:27

Я не пойму что-то. Вы типа научились за линейное время находить наидлиннейший палиндром для каждой буквы, и теперь никак не можете найти все под-палиндромы? Или чего?
Ответить с цитированием
Ads.
  (#36 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 18.01.2009, 21:30

Мы научились находить количество длиннейших палиндромов в строке (это тривиально). Теперь не можем решить задачу...
Ответить с цитированием
Ads
  (#37 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 19.01.2009, 05:30

Да, а длинну-то, длинну этих длиннейших вы тоже находите или что?
Ответить с цитированием
  (#38 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 19.01.2009, 15:11

Нет. Только общее количество.
Ответить с цитированием
  (#39 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 19.01.2009, 20:45

У меня пояилась идея, как это сделать быстро, когда я ехал на работу, но поскольку ты объявил, что решил задачу, я посчитал, что реализовывать её неинтересно, и теперь я её не помню...
Ответить с цитированием
  (#40 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 19.01.2009, 23:57

Кошмар, я уже испытал угрызения совести Больше не надо...
Ответить с цитированием
  (#41 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 20.01.2009, 05:42

Цитата:
Нет. Только общее количество.
Вообще ни фига не понял. В книжке, кажется, описано что-то про поиск наидлиннейших палиндромов для каждой буквы, их количество по определению равно числу букв. Берём очередную букву, если максимальный палиндром с центром в этой букве имеет длину N, то к общему числу палиндромов для строки прибавляем (N-1)/2 + 1, или как-то так.

А вы что подразумеваете под "их общим количеством"??
Ответить с цитированием
  (#42 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 20.01.2009, 08:49

В том-то и дело, что количество наидлиннейших подпалиндромов мы находим, а вот длину каждого из них - нет. А если искать ещё и длину (за линейное время), то поиск палиндрома за линейное время+поиск его длины за линейное время - получиться квадрат.
Ответить с цитированием
  (#43 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 20.01.2009, 09:06

Что такое "количество наидлиннейших палиндромов"? Для каждой буквы (и для каждой пары букв) будет только 1 (один) наидлиннейший палиндром с центром в этой букве. Что там искать-то??? Их количество равно количеству букв в строке. Ну плюс отдельно для палиндромов чётной длины почти то же самое.
Ответить с цитированием
  (#44 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 20.01.2009, 19:45

ну одну букву я палиндромом не считаю. А так - ты прав.
Ответить с цитированием
  (#45 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 21.01.2009, 10:06

Т. е., фраза "количество наидлиннейших подпалиндромов мы находим" означает "мы считаем количество букв в строке"?
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Не могу найти ошибку. Помогите найти и исправить... 111 Pascal 0 12.01.2011 16:30
TListBox требуется найти в строке слово и похожее к нему слово qqeeaaddzzcc_the_same C++ Builder 2 28.01.2009 23:32
Требуется найти ошибку J2ME Kirkh J2ME 3 12.11.2008 14:26
Требуется mirra Работа 0 17.03.2008 13:48
Не могу найти звуковой дарайвер на материнскую плату P4V845, помогите найти. lev3315 Техническая поддержка 3 23.05.2007 02:15
Требуется найти наименьшее число krumaks Pascal 8 25.12.2005 14:43
ODBC требуется найти примеры Angel5a WinAPI 0 29.10.2005 14:08
Требуется найти ошибку в Javascript-коде Necrosis DHTML, JavaScript, VBScript 3 16.02.2005 10:25
Требуется найти заданную последовательность в строке Pitch Lisp 1 10.10.2004 15:32
Требуется найти внутри html-документа определенный фрагмент и удалить его Kalinich Visual C++ 1 29.07.2004 10:38
Где найти найти MySQL драйвера для dbExpress Anonymous C++ Builder 4 05.01.2004 19:46
Требуется Java developer где найти в интернете Anonymous Java 0 16.12.2003 20:22



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов