[Moscow.pm] Ускорение регэкспа

[Anton Nikishaev]

On Jul 12, 2013, at 10:43 AM, "Konstantin S. Uvarin" <khedin at gmail.com> wrote:

> Приветствую! 
> 
>  Как вариант: пилим строку субстрами, начиная с *каждого* символа, и
> строим хеш: 
> 
>  { 15_символов_подряд => [ вхождение, вхождение2, ... ] }
> 
>  Затем все ключи, указывающие на массив <5 просто выкидываем, а
> остальные проверяем, что они не слишком "тесные" (и выкидываем 
> лишние вхождения).
> 
>  Памяти сожрёт много, зато время, кажется, около линейного.
> 


Скорей O(n log n).

Вообще можно построить suffix tree, там сразу видно что повторяется и сколько раз.
Если нам плевать на перекрытия повторяющихся кусков можно ускориться до O(n)



>> Здравствуйте.
>> 
>> Есть регэксп /(.{15})(.+\1){5}/o . Написан, чтобы искать повторяющиеся
>> 6 раз и более подстроки длинной 15 и более символов. На большом 
> тексте
>> работает  очень  долго,  что объяснимо. Как бы его ускорить или 
> решить
>> задачу иначе?
>> 
>> -- 
>> С уважением,
>> Михаил                          mailto:postmaster at softsearch.ru
>> 
>> -- 
>> Moscow.pm mailing list
>> moscow-pm at pm.org | http://moscow.pm.org
>> 
> 
> --
> WBR,
> Konstantin S. Uvarin
> -- 
> Moscow.pm mailing list
> moscow-pm at pm.org | http://moscow.pm.org