On Sat, Sep 05, 2009 at 02:52:50AM -0700, staafmeister wrote:
> How would experienced haskellers solve this problem?
You could just memoize using an array, like in C.
import Data.Array
occurrences :: Num a => String -> String -> a
occurrences key buf = grid ! (0, 0) -- grid ! (i, j) = occurrences (drop i
key) (drop j buf)
where grid = listArray ((0, 0), (nk, nb)) [
if i == nk then 1
else if j == nb then 0
else (if key !! i == buf !! j then grid ! (i+1, j+1) else 0) +
grid ! (i, j+1)
| i <- [0..nk], j <- [0..nb]
]
nk = length key
nb = length buf
Regards,
Reid
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
