Тема: Суффиксный массив
здесь в форумах многие писались про массив суффиксов,
можно ли написать как искать lcp двух суффиксов за O(log(LEN)) и использовании O(LEN) памяти,а то я только умею как при помощи O(LENlog(LEN)) памяти.
Re: Суффиксный массив
а нельзя так? хранишь для каждого p[ i ] и p[ i + 1 ] ( суффиксный массив ) их LCP. то есть такой массив есть. на нем мы построим дерево фенвика (минимумов). Тогда запрос LCP( i, j ) - наибольший общий префикс подстрок с началами i < j соответственно - это запрос минимума p2[ i ], p2[ j - 1 ], где p2[ i ] - положение i - ого суффикса в суф массиве. Вроде работает за O( logN ) запрос, а памяти O( N ). Вроде ничего не путаю.
Re: Суффиксный массив
Предлагаю,отписывать где нибудь интересующие всех алгоритмы,какие нибудь необычные,или очень полезные,и опубликовывать их на сайте для повышения кол-ва алгоритмов,тогда этот сайт действительно станет великолепным 
Re: Суффиксный массив
)) +1 )) просто написали - я ответил)) наверное стоит перенести сообщения в ветку обсуждения алгоритмов)
Re: Суффиксный массив
а откуда именно взят алгоритм построения суффиксного массива?
Re: Суффиксный массив
может, отсюда?
http://e-maxx.ru/algo/
Re: Суффиксный массив
я о первоисточнике