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

Цитата:
Еще есть мысль - попробовать взять исходную строку, перевёрнутую строку и поискать совпадения...
Это первое, о чём я подумал - там тоже квадрат получается и вообще - метод сводится к тому, что я написал...
Ответить с цитированием
  (#17 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 08.01.2009, 23:23

Эй, ProgZ!!! Идеи есть?
Ответить с цитированием
  (#18 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 09.01.2009, 05:56

Книга называется "Algorithms on Strings, Trees, and Sequences", автор Dan Gusfield. Щас посмотрел - там есть небольшой раздел про поиск всех максимальных палиндромов - написано, что можно найти за линейное время. Если так, то, зная длину максимального палиндрома для каждой буквы, количество всех остальных палиндромов для этой же буквы выражается примитивной формулой от этой длины. Алгоритм основывается как раз на сравнении исходной и перевёрнутой строк, точнее - на поиске наибольших общих продолжений, так сразу фиг чего поймёшь. Книги в djvu (12 Мб, на русском) у меня, конечно, нет, да ты и сам бы не захотел, потому что пиратство - это очень плохо, но если вдруг всё же хочешь - скажи е-мэйл, я тебе пришлю брошюру о вреде пиратства (по странному совпадению, она тоже 12 Мб djvu и на русском)
Ответить с цитированием
  (#19 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 09.01.2009, 11:44

И мне вышли.
Мой адрес Stebanoid на gmail точка ком

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

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

Ага, щазз! Это ж мне его надо подробно прочитать для этого, а то и понять...
Ответить с цитированием
  (#22 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,281
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 09.01.2009, 14:48

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

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

http://drop.io/q96lqln
На самом деле там не архив, просто переименуйте в .djvu и открываете вьюером. Лучший вьюер этого формата, который я знаю - http://windjview.sourceforge.net/
Ответить с цитированием
Ads
  (#25 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 10.01.2009, 14:20

Сейчас посмотрю, што это
Ответить с цитированием
  (#26 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 11.01.2009, 19:40

Автор уверен, что в слове
bbacabv
Подпалиндромами являются и aca и bacab? Или всё-таки считается именно наидлиннейший?
Потому что по второму случаю можно сделать линейный алгоритм очень просто.
Ответить с цитированием
  (#27 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 14.01.2009, 22:16

Все. А что с наидлиннеёшим? Что-то мне не приходит в голову линейка...
Ответить с цитированием
  (#28 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 15.01.2009, 01:06

Что всё? рассказывай, как сделал.
Ответить с цитированием
  (#29 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 15.01.2009, 20:01

Не всё, а все. Все палиндромы надо искать. Насчёт сделал - вроде прокатило предыдущий вариант... никто не заметил... но самому до сих пор интересно.
Ответить с цитированием
  (#30 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 17.01.2009, 00:22

А с наидлиннейшим всё элементарно - любой палиндром содержит в ередине кусок типа xx или xyx. Проходим по всему списку один раз и считаем такие участки.
Ответить с цитированием
Ответ

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

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

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 - компьютерный форум и программирование, форум программистов