On 19/03/10 20:41, ivovnenko wrote:
Hi. I tried to solve one of the google code jam's problems using haskel http://code.google.com/codejam/contest/dashboard?c=90101#s=p2:
w :: Eq a => [a] -> [a] -> Int w text str = w' (reverse text) (reverse str) w' :: Eq a => [a] -> [a] -> Int -- Init w' _ [] = 0 w' [] _ = 0 -- For one symbol string w' text [a] = if head text == a then w' (tail text) [a] +1 else w' (tail text) [a] -- General case w' text str = if head str == head text then w' (tail text) (tail str) + w' (tail text) str else w' (tail text) str
and it worked great on small inputs, not on large:
I suspect that a change of type for w' would improve things a bit. The base cases: w' n [] _ = n w' n _ [] = n w' n (t:ts) [a] = if t == a then w' (succ n) ts [a] else w' n ts [a] After reading the problem description though I think that thinking hard about the problem might reveal that there's a more clever way to solve it instead of the rather brute-force route you've taken so far. /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe