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

From: Kanishk (kanishk509_at_[hidden])
Date: 2020-10-31 08:38:43

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