Poking through some of my old delicious links, I found a post about finding palindromes in O(n) time that I'd always meant to come back to, but never did.
So I played around with it during my vacation to Virginia Beach with my family this year.
It took me a while to grok the algorithm in full, but once I did, I realized that it could be adapted to operate on list input (rather than array input) and produce results lazily. This has the benefit of being able to do stuff like take 100 . maximalPalindromeLengths $ repeat (), but I haven't thought of any practical benefit yet, since it still requires O(n) memory, so it's not appropriate for streaming data.
Here's my variation, though it's in a real repos if you want to play around with it:
1 comment:
Nice solution!
I've now compared your lazy solution with my random-access solution using Criterion on the text of the King James' Bible. It turns out that the random access solution is about 1.7 times faster under unoptimized compilation. Using -O2 makes both solutions go slower.
Post a Comment