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?
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\ \elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove\ \ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl\ \ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI\ \tisforusthelivingrathertobededicatedheretotheulnfinishedwor\ \kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather\ \forustobeherededicatedtothegreattdafskremainingbeforeusthat\ \fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh\ \ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres\ \olvethatthesedeadshallnothavediedinvainthatthisnationunsder\ \Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb\ \ythepeopleforthepeopleshallnotperishfromtheearth" main :: IO () main = B.putStrLn $ longestPalindrome gettysburg
As expected, we get ranynar as the answer. Sure, it’s an O(n3) algorithm, but since this is a fairly short text it doesn’t matter all that much, as evidenced by the half-second running time. If you’re working with longer inputs, use a different algorithm.