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\
    \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.

About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: