Реализации алгоритмов/Наибольшая общая подпоследовательность: различия между версиями

{{wikipedia|Наибольшая общая подпоследовательность}}

 

import Data.Function

import Data.List

yoba listY listX = reverse $ arr ! (lenY, lenX)

where lenY = length listY

lenX = length listX

arrY = listArray (1, lenY) listY

arrX = listArray (1, lenX) listX

arr = listArray ((0, 0), (lenY, lenX)) [value y x | y <- [0 .. lenY], x <- [0 .. lenX]]

value y x | y == 0 || x == 0 = []

| otherwise = maximumBy (compare `on` length) [arr ! (y, pred x), arr ! (pred y, x)]

main = print $ yoba "aaaaabbbb34354354345" "abbb34aaabbbb"

</source>