Ir al contenido principal

Segmentos comunes maximales

Los segmentos de de "abcd" son

["","a","ab","abc","abcd","b","bc","bcd","c","cd","d"]

Los segmentos comunes de "abcd" y "axbce" son

["","a","b","bc","c"]

Los segmentos comunes maximales de "abcd" y "axbce" son

["a","bc"]

Definir la función

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

tal que (segmentosComunesMaximales xs ys) es la lista de los segmentos comunes maximales de xs e ys. Por ejemplo,

segmentosComunesMaximales "abcd" "axbce"  ==  ["a","bc"]

Soluciones

import Data.List (inits, tails, isInfixOf)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales xs ys =
  [zs | zs <- zss
      , [us | us <- zss, zs `isInfixOf` us] == [zs]]
  where zss = segmentosComunes xs ys

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]
segmentosComunes xs ys =
  [zs | zs <- segmentos xs
      , zs `isInfixOf` ys]

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,
--    segmentos "abc"  ==  ["","a","ab","abc","b","bc","c"]
segmentos :: [a] -> [[a]]
segmentos xs =
  [] : concatMap (tail . inits) (init (tails xs))

[/schedule]