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