Подпалиндромы требуется найти чилсо - Страница 3

Exmap · 17.01.2009, 22:58

Ну в общем ты прав... А надо все...

Exmap · 18.01.2009, 13:50

Я понял!!! Я сделал за O(n lg n)!
При нахождении двух (или одной) одинаковых букв алгоритмом Кошмара мы двоичным поиском ищем границы!!!!!!!!!!!!!
Блин, как я сразу не догадался... Уже скормил квадрат...

Кошмар · 18.01.2009, 14:51

wvbcsdabadrcbg

находим aba, затем двоичным поиском находим границу b...b, итого нашли подпалиндром
bcsdabadrcb
хотя он таковым не является, потому что s не равно r.
А если проверять все буквы подряд - то будет опять то, с чего мы начинали.

Exmap · 18.01.2009, 16:15

А... ну в общем - да, я поторопился.

Vladimir the Red Sunny · 18.01.2009, 17:27

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

Exmap · 18.01.2009, 21:30

Мы научились находить количество длиннейших палиндромов в строке (это тривиально). Теперь не можем решить задачу...

Vladimir the Red Sunny · 19.01.2009, 05:30

Да, а длинну-то, длинну этих длиннейших вы тоже находите или что?

Exmap · 19.01.2009, 15:11

Нет. Только общее количество.

Кошмар · 19.01.2009, 20:45

У меня пояилась идея, как это сделать быстро, когда я ехал на работу, но поскольку ты объявил, что решил задачу, я посчитал, что реализовывать её неинтересно, и теперь я её не помню...

Exmap · 19.01.2009, 23:57

Кошмар, я уже испытал угрызения совести

Больше не надо...

Vladimir the Red Sunny · 20.01.2009, 05:42

Цитата:

Нет. Только общее количество.

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

А вы что подразумеваете под "их общим количеством"??

Кошмар · 20.01.2009, 08:49

В том-то и дело, что количество наидлиннейших подпалиндромов мы находим, а вот длину каждого из них - нет. А если искать ещё и длину (за линейное время), то поиск палиндрома за линейное время+поиск его длины за линейное время - получиться квадрат.

Vladimir the Red Sunny · 20.01.2009, 09:06

Что такое "количество наидлиннейших палиндромов"? Для каждой буквы (и для каждой пары букв) будет только 1 (один) наидлиннейший палиндром с центром в этой букве. Что там искать-то??? Их количество равно количеству букв в строке. Ну плюс отдельно для палиндромов чётной длины почти то же самое.

Кошмар · 20.01.2009, 19:45

ну одну букву я палиндромом не считаю. А так - ты прав.

Vladimir the Red Sunny · 21.01.2009, 10:06

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

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Не могу найти ошибку. Помогите найти и исправить...	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

Exmap Member Сообщений: 1,045 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 17.09.2007	17.01.2009, 22:58 Ну в общем ты прав... А надо все...

Exmap Member Сообщений: 1,045 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 17.09.2007	18.01.2009, 13:50 Я понял!!! Я сделал за O(n lg n)! При нахождении двух (или одной) одинаковых букв алгоритмом Кошмара мы двоичным поиском ищем границы!!!!!!!!!!!!! Блин, как я сразу не догадался... Уже скормил квадрат...

Exmap Member Сообщений: 1,045 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 17.09.2007	18.01.2009, 16:15 А... ну в общем - да, я поторопился.

Vladimir the Red Sunny Member Сообщений: 4,232 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 15.05.2003	18.01.2009, 17:27 Я не пойму что-то. Вы типа научились за линейное время находить наидлиннейший палиндром для каждой буквы, и теперь никак не можете найти все под-палиндромы? Или чего?

Exmap Member Сообщений: 1,045 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 17.09.2007	18.01.2009, 21:30 Мы научились находить количество длиннейших палиндромов в строке (это тривиально). Теперь не можем решить задачу...

Vladimir the Red Sunny Member Сообщений: 4,232 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 15.05.2003	19.01.2009, 05:30 Да, а длинну-то, длинну этих длиннейших вы тоже находите или что?

Exmap Member Сообщений: 1,045 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 17.09.2007	19.01.2009, 15:11 Нет. Только общее количество.

Кошмар Member Сообщений: 2,694 Сказал(а) спасибо: 0 Поблагодарили 1 раз в 1 сообщении Регистрация: 23.04.2005	19.01.2009, 20:45 У меня пояилась идея, как это сделать быстро, когда я ехал на работу, но поскольку ты объявил, что решил задачу, я посчитал, что реализовывать её неинтересно, и теперь я её не помню...

Exmap Member Сообщений: 1,045 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 17.09.2007	19.01.2009, 23:57 Кошмар, я уже испытал угрызения совести Больше не надо...

Кошмар Member Сообщений: 2,694 Сказал(а) спасибо: 0 Поблагодарили 1 раз в 1 сообщении Регистрация: 23.04.2005	20.01.2009, 19:45 ну одну букву я палиндромом не считаю. А так - ты прав.

Ads

Vladimir the Red Sunny Member Сообщений: 4,232 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Регистрация: 15.05.2003	21.01.2009, 10:06 Т. е., фраза "количество наидлиннейших подпалиндромов мы находим" означает "мы считаем количество букв в строке"?