Longest palindromic substrings: Difference between revisions
m
→{{header|Haskell}}: Added a list-based draft in Haskell. An indexed datatype would allow for something faster.
Thundergnat (talk | contribs) m (→{{header|Raku}}: typo) |
m (→{{header|Haskell}}: Added a list-based draft in Haskell. An indexed datatype would allow for something faster.) |
||
Line 89:
abaracadaraba Length 3 -> [aba aca ada ara]
</pre>
=={{header|Haskell}}==
A list version, written out of curiosity. A faster approach could be made with an indexed datatype.
<lang haskell>-------------- LONGEST PALINDROMIC SUBSTRINGS ------------
longestPalindromes :: String -> ([String], Int)
longestPalindromes s = (filter ((w ==) . length) xs, w)
where
xs = palindromes s
w = maximum $ length <$> xs
palindromes :: String -> [String]
palindromes = fmap go . palindromicNuclei
where
go (pivot, (xs, ys)) =
let suffix = fmap fst (takeWhile (uncurry (==)) (zip xs ys))
in reverse suffix <> pivot <> suffix
palindromicNuclei :: String -> [(String, (String, String))]
palindromicNuclei s = contexts >>= go
where
contexts = (init . tail) (zip prefixes suffixes)
prefixes = scanl (flip ((<>) . return)) [] s
suffixes = scanr (:) [] s
go (a@(x:_), b@(h:y:ys)) =
if x == h
then [("", (a, b))]
else [ ([h], (a, y : ys))
| x == y ]
go _ = []
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
fTable
"Longest palindromes substrings:\n"
show
show
longestPalindromes
[ "three old rotators"
, "never reverse"
, "stable was I ere I saw elbatrosses"
, "abracadabra"
]
------------------------ FORMATTING ----------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String
fTable s xShow fxShow f xs =
unlines $
s : fmap (((++) . rjust w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs
where
rjust n c = drop . length <*> (replicate n c ++)
w = maximum (length . xShow <$> xs)</lang>
{{Out}}
<pre>Longest palindromes substrings:
"three old rotators" -> (["rotator"],7)
"never reverse" -> (["ever reve"],9)
"stable was I ere I saw elbatrosses" -> (["table was I ere I saw elbat"],27)
"abracadabra" -> (["aca","ada"],3)</pre>
=={{header|Julia}}==
| |||