[Algorithm] Implementing: Find Longest Palindromic Substring(Sub-vector).

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[Algorithm] Implementing: Find Longest Palindromic Substring(Sub-vector).

Boost - Dev mailing list
Hello all,

I'm new to the Boost community and this is my first time posting to the
mailing group.
What brought me here: I'm a Computer Science student and I often have to
code up string/sequence related algorithms. An algorithm that I found was
missing from the boost libraries was "Find Longest Palindromic Substring(or
generic Sub-vector)".

Boost has *is_palindrome *(
but using that to check every possible substring will result in an O(N^3)
runtime. It is trivial to implement an O(N^2) algorithm for this purpose
using dynamic-programming. It is also possible to implement this in O(N)
using the Manacher's algorithm (

Will this be a useful addition to the Boost.Algorithm library? If so, I
would love to start contributing to boost through this.

Regards, Kanishk

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost