Boost logo

Boost :

Subject: Re: [boost] Project Idea for 2014 GSoC
From: Piotr Wygocki (vwygos_at_[hidden])
Date: 2014-02-20 09:07:54

Hi, actually suffix array can be computed in O(n) time.

The paper describing this algorithm:

the paper includes some implementation as well.

Of course it might be the case that O(n log n) implementation is faster for
practical cases.

Regards and Good Luck!


On 20 February 2014 13:54, Prabhat Kumar <dawnavd_at_[hidden]> wrote:

> Hello,
> In forthcoming google summer of code I'm thinking of implementing *Suffix
> Array* data structure.
> As a data structure, it is widely used in areas such as data compression,
> bioinformatics and, in general, in any area that deals with strings and
> string matching problems. So I think It would be very cool to add this data
> structure in Boost Libraries.
> Here is some brief description of some method which I have planned so far
> :-
> 1) Creation of Suffix array in O(n log n ), there is a relatively easy
> implementation in O(n (log n)^2) using STL's sort function, but radix sort
> we can achieve O(n log n) .... :)
> 2) Longest common prefix of any two suffix in O (log n)
> 3) Total distinct substring of given string in O(n log n)
> I'll be glad to hear some suggestion.
> Prabhat Kumar
> Indian Institute of Information Technology, Allahabad , India
> _______________________________________________
> Unsubscribe & other changes:

Boost list run by bdawes at, gregod at, cpdaniel at, john at