Programming Praxis – Longest Duplicated Substring

In today’s Programming Praxis exercise, our task is to implement the algorithm to find the longest duplicated substring in a word. Let’s get started, shall we?

Some imports:

import Data.List
import Data.List.HT (mapAdjacent)
import qualified Data.List.Key as K

It seems we have yet another case of simply translating the English description to Haskell syntax: create a list of suffixes, sort, get the longest common prefix of all adjacent pairs and return the longest one.

lds :: Ord a => [a] -> [a]
lds = K.maximum length . mapAdjacent lcp . sort . tails where
    lcp (x:xs) (y:ys) | x == y = x : lcp xs ys
    lcp _      _               = []

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ lds "banana"
          print $ lds "ask not what your country can do for you, \
                      \ask what you can do for your country"

Everything seems to be working fine.

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: