поиск последовательностей

← →
robt5 (2013-12-24 17:30) [40]

> jumping jack (24.12.13 14:02) [34]

да, по всем пунктам кроме вывода
вывод пока неактуален

> не тормоз (24.12.13 14:11) [35]

нет не архиватор, но подобный "словарь" близок к идее (ты реально не тормоз)

← →
не тормоз (2013-12-24 19:06) [41]

да я в курсе.
я же медвежонок пятачок.

← →
jumping jack (2013-12-24 19:55) [42]

ну вроде не архисложно
с получением каждого нового символа/числа добавляем его не в конец, а в начало буфера и ищем начинающуюся с него последовательность с разными смещениями, наращивая смещение по единичке в цикле, начиная с 2 или заданного минимума и заканчивая половиной размера всего полученного или заданным максимумом
(конечно, новополученное проще добавлять не в начало, а в конец буфера, но тогда искать нужно "задом наперед")
это примитивный алгоритм, для ускорения можно применить Бойера-Мура - описан в первой ссылке в [8]

← →
картман © (2013-12-24 20:47) [43]

> jumping jack (24.12.13 19:55) [42]
>
> ну вроде не архисложно

но архивычислительно

← →
jumping jack (2013-12-24 21:43) [44]

тупой алгоритм - да, сложность кубическая
но если 1) применить Бойера-Мура и 2) ограничить глубину поиска и длину искомого, то как бы все степени мы убираем, то есть осталась простая пропорция к длине последовательности, хоть и с большим коэффициентом
архиваторы ведь как-то справляются со сложностью - нет там степеней-то, чистые мегабайты в секунду

поиск последовательностей Найти похожие ветки