Re: [boost] Project Idea for 2014 GSoC

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:

http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf

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!

Piotr

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:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>