[boost] Project Idea for 2014 GSoC

Subject: [boost] Project Idea for 2014 GSoC
From: Prabhat Kumar (dawnavd_at_[hidden])
Date: 2014-02-20 07:54:48

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