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.

Tags: , , , , , , , ,

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: