On Jul 12, 2013, at 10:43 AM, "Konstantin S. Uvarin" <[email protected]> wrote:
> Приветствую!
>
> Как вариант: пилим строку субстрами, начиная с *каждого* символа, и
> строим хеш:
>
> { 15_символов_подряд => [ вхождение, вхождение2, ... ] }
>
> Затем все ключи, указывающие на массив <5 просто выкидываем, а
> остальные проверяем, что они не слишком "тесные" (и выкидываем
> лишние вхождения).
>
> Памяти сожрёт много, зато время, кажется, около линейного.
>
Скорей O(n log n).
Вообще можно построить suffix tree, там сразу видно что повторяется и сколько
раз.
Если нам плевать на перекрытия повторяющихся кусков можно ускориться до O(n)
>> Здравствуйте.
>>
>> Есть регэксп /(.{15})(.+\1){5}/o . Написан, чтобы искать повторяющиеся
>> 6 раз и более подстроки длинной 15 и более символов. На большом
> тексте
>> работает очень долго, что объяснимо. Как бы его ускорить или
> решить
>> задачу иначе?
>>
>> --
>> С уважением,
>> Михаил mailto:[email protected]
>>
>> --
>> Moscow.pm mailing list
>> [email protected] | http://moscow.pm.org
>>
>
> --
> WBR,
> Konstantin S. Uvarin
> --
> Moscow.pm mailing list
> [email protected] | http://moscow.pm.org
--
Moscow.pm mailing list
[email protected] | http://moscow.pm.org