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

Требуется найти число подпалиндромов данной строки (то есть подстрок, являющихся палиндромами). Пробовал и наивно за O(n^2) - перебираешь серединку палиндрома... По времени долго для больших файлов. Может, можно быстрее? Помогите с алгоритмом.
Ответить с цитированием
  (#2 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 08.01.2009, 11:51

Вот почти O(n):

Код:
def step(string,n1,n2): #функция принимает строку и два числа - номера левого и правого элемента очередного подпалиндрома
    nn1=n1-1 # расширим границы
    nn2=n2+1
    if nn1<0 or nn2>len(string)-1 or string[nn1]!=string[nn2]: # проверим выход за пределы строки и является ли палиндромом
        return string[n1:n2+1] # если нет - вернём палиндром
    else:
        return step(string,nn1,nn2) #если да - рекурсивно будем увеличивать палиндром

def podpal(string): #основная функция - принимает строку
    L=[] # создали пустой список
    for x in xrange(len(string)-1): # для х от 0 до длиннастроки-1
        if string[x]==string[x+1]: # если два соседа близнецы - то ищем здесь палиндром
            L.append(step(string,x,x+1)) # и добавим его в список
    for x in xrange(len(string)-2): # то же, если одинаковые элементы через один, например "aba"
        if string[x]==string[x+2]:
            L.append(step(string,x,x+2))
    return L
если что не понятно - спрашивай.
Ответить с цитированием
  (#3 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 08.01.2009, 12:11

Кошмар, требуется найти КОЛИЧЕСТВО подпалиндромов. Например, для abacaba - ответ 12
1. a
2. b
3. a
4. c
5. a
6. b
7. a
8. aba
9. aba (в другом месте)
10. aca
11. bacab
12. abacaba


Но твой алг - подобие моего. В моём наивном алгоритме перебирается (как у тебя) середина палиндрома и для каждой середины считается число палиндромов. Но это O(n^2) - например, если у тебя 100 000 одинаковых букв - то это уже фигня
Проверено на простенькой программке:
Код:
var i,k,j:longint;
begin
 for k:=1 to 2 do
  for i:=1 to 50000 do
   for j:=1 to i do;
end.
Судя по всему требуется решение за O(n log n), так как максимальное n - 100 000.
Ответить с цитированием
  (#4 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 08.01.2009, 13:19

Цитата:
Но это O(n^2) - например, если у тебя 100 000 одинаковых букв - то это уже фигня
Если палиндромов мало, как в обычном тексте, то O(N). Я исходил из этого.
Если все буквы одинаковые, то кол-во палиндромов само по себе растёт квадратично.. Ты хочешь сделать скорость роста времени подсчёта их количества, меньше, чем скорость роста количества палиндромов? Не стану утверждать, что это невозможно, но что-то я сомневаюсь...
Ответить с цитированием
  (#5 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 08.01.2009, 13:58

Кошмар, не обязательно на очередном шаге алгоритма увеличивать число палиндромов на 1. Я имею ввиду - не обязательно их считать по 1. Я знаю, что есть решение, которое укладывается в time-limit = 2 с и работает при n<=100 000
Твоё решение (оно же и моё решение) работает за O(n+k) где k - число палиндромов. Но так как k=O(n^2), O(n+k)=O(n^2) - увы, не проходит... Эх, за энлогэн бы...
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 08.01.2009, 14:01

Цитата:
перебираешь серединку палиндрома
Это что значит? От каждой буквы идёшь в обе стороны до тех пор, пока образуются новые палиндромы?
Ответить с цитированием
  (#7 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 08.01.2009, 14:36

Цитата:
От каждой буквы идёшь в обе стороны до тех пор, пока образуются новые палиндромы?
Похоже да. - смотри мою реализацию, у него примерно так же.

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

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

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

Цитата:
Ну моя реализация тоже 5Мб файл за какие-то доли секунды перелопатила...
Кошмар, 5 метров букв 'a' она вряд ли так быстро съест
Ответить с цитированием
  (#11 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 08.01.2009, 16:49

Цитата:
А есть другие идеи?
У меня есть идея, но она какая-то не в меру навороченная и я не уверен, что она: а) будет работать вообще, б) будет эффективнее, даже если будет работать, в) чем-то серьёзно отличается по сути от "поиска с середины"

Идея в том, чтобы проиндексировать все буквы, каждую в отдельный массив, т. е., допустим, для abacaba это будет:

a: 0, 2, 4, 6
b: 1, 5
c: 3

Массив этих массивов отсортировать по возрастанию первого индекса, буквы можно вообще выкинуть. Искать наоборот - не с середины, а с краёв - если края не идентичны, то это всё равно уже не палиндром. Для a в нулевой позиции потенциальные палиндромы будут (0, 2), (0, 4), (0, 6). Интервал (x, y) будет палиндромом только тогда, когда среди наших массивов с "индексами" будет такой, который содержит элементы (x+1, y-1), такой, который содержит (x+2, y-2) и т. д., до некоторого шага n, равного разнице между первоначальными позициями, когда x+n == y-n (массив должен содержать один этот элемент). Более того, т. к. массивы отсортированы по первому индексу, приращение x можно тоже отбросить, проверять ВСЕ массивы на то, содержат ли они y-1 не надо - т. е., достаточно взять следующий массив, проверить, содержит ли он y-1, если да - взять снова следующий, проверить, содержит ли он y-2 и т. д. (особый случай, когда очередной x содержится в первом массиве). Если еще всё это сунуть в битсеты - вообще быстро должно быть. Влево искать мы никогда не будем, поэтому после проверки всех пар для 0 в строке для a, мы удаляем этот 0 оттуда и пересортировываем наши массивы опять по первому индексу (т. е., достаточно переставить первый массив на его новое место) и повторяем. Ну и там опять же специальные случаи, когда (y-x) < 3 - это всегда палиндром, и если в результате исходной индексации у нас получился всего один массив - там наверняка есть какая-то уже готовая формула

Пример для abacaba:

0, 2, 4, 6
1, 5
3
(сами буквы нам уже не важны)
Первый интервал (0, 2), значит, в следующей строке должно быть 1 - да, палиндром. Следующий интервал - (0, 4), в следующей строке должно быть 3 - нет, не палиндром. Следующий интервал - (0, 6), в следующей строке должно присутствовать 5 (которое на самом деле (1, 5), но мы можем игнорировать 1, т. к. он не входит в первую строку) - да, теперь должно быть 4, 2 у нас в первой строке, поэтому ищем 4 там же - да, теперь в следующей (после той, где было 5) должно быть 3 (которое на самом деле (3, 3)) - да, присутствует, числа сравнялись - дальше проверять не надо, это палиндром.

Выкидываем 0, получаем:

2, 4, 6
1, 5
3

Сортируем по первому индексу, получаем (это мы, по-сути, уже проверяем bacaba - для первой a мы нашли все палиндромы):

1, 5
2, 4, 6
3

Первый (и единственный) интервал в первой строке - (1, 5), во второй должно быть 4 - да, в третьей должно быть 3 - да, стоп, палиндром.

Выкидываем 1, сортируем (acaba) -

2, 4, 6
3
5

(2, 4), 3 - палиндром.

caba
3
4, 6
5

Если в первой строке только один элемент - его надо выкинуть, потому что интервалов не осталось.

aba

4, 6
5

(4, 6), 5 - да, палиндром.

ba

5
6

Выкидываем 5, потом по тому же правилу выкидываем 6. Всё. Теперь к результату прибавить общее число букв в строке (каждая буква - сама себе палиндром) - и готово.

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

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

Vladimir, прога ведёт себя скверно опять на том же тесте - куча одинаковых букв. Сам посуди, чистой воды квадрат.
И ещё. Уже было сказано, что ответ больше, чем доступного времени. То есть решение за W(k) *омега от k - нижний предел* не принимаются (тут k - ответ на задачу). Надо считать их группами. В каждой итерации находить группу палиндромов.
Ответить с цитированием
  (#14 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 08.01.2009, 20:52

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

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

Vladimir, я реализовал. Верхняя оценка обоих случаев O(n^2), а вот в среднем твой подход лучше. Правда, я там пару строчек модифицировал... И вроде бы тест на корректность тоже пройден. Что за книга? Я-то в своём кормене да в томах кнута всё выискиваю...
Ответить с цитированием
Ответ

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

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

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