[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 *(
https://www.boost.org/doc/libs/1_66_0/boost/algorithm/is_palindrome.hpp),
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 (
https://en.wikipedia.org/wiki/Longest_palindromic_substring#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