## Programming Praxis – Find The Longest Palindrome In A String

In today’s Programming Praxis exercise, our goal is to write an alogrithm to find the longest palindrome in a string. Let’s get started, shall we?

Some imports:

import qualified Data.ByteString.Char8 as B
import qualified Data.List.Key as K

Since the exercise is originally part of a group of 3 that is supposed to be completed in 20 minutes to 2 hours, I’m going to assume I don’t have time to figure out a fancy but complicated suffix trie-based approach. Below is the version I wrote in a minute or two, with two modifications:

1. The list comprehensions was originally a filter and a concatMap. Same thing, but different syntax. I like this version better.
2. The original worked on plain strings and ran in 8 seconds or so. Switching to ByteStrings speeds things up quite a bit and is trivial to do, requiring only a few additions of “B.”.

The algorithm is pretty trivial: get every possible substring, check if it’s a palindrome and return the longest one.

longestPalindrome :: B.ByteString -> B.ByteString
longestPalindrome s = K.maximum B.length
[p | p <- B.inits =<< B.tails s, p == B.reverse p]

We test the algorithm on the Gettysburg Address.

gettysburg :: B.ByteString
gettysburg = B.pack
"Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta\
\inentanewnationconceivedinzLibertyanddedicatedtotheproposit\
\ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa\
\rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic\
\atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh\
\avecometodedicpateaportionofthatfieldasafinalrestingplacefo\
\rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog\
\etherfangandproperthatweshoulddothisButinalargersensewecann\
\otdedicatewecannotconsecratewecannothallowthisgroundThebrav\
\ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI\
\tisforusthelivingrathertobededicatedheretotheulnfinishedwor\