The problem is to count all possible sub-sequences of welcome to code jam in a given input string (and only return the last 4 digits of the count).  Here is the link to the problem for reference.I've implemented a solution in Haskell that worked fine on the examples and small datasets but failed on the large data set. Here is the code:I'm interested in correctness first. (Am I missing some corner case?) I guess performance can be improved by memoization; and I'd be happy get any other tips on that front too.w_s is short for welcome_solve: This calculates the total number of sub-sequences.w_s x [] = 0w_s (x: []) str_xs = length ( filter (\z -> z==x) str_xs ) w_s (x:xs) (str_x:str_xs) = if x==str_x                            then (w_s xs str_xs)  + (w_s (x:xs) str_xs)                             else w_s (x:xs) str_xsAnd here is the code to get the last 4 digits:getLast4 (w:x:y:z: []) = [w,x,y,z]getLast4 (x:xs) = getLast4 xsformat_solve problem          | solution < 1000 = getLast4 $ show $ 10000 + solution         | otherwise  = getLast4 $ show solution         where solution = w_s welcome to code jam problemExample usage:> format_solve format_solve welcome to codejam0000> format_solve wweellccoommee to code qps jam0256> format_solve elcomew elcome to code jam0001
Google Code jam puzzle - Welcome to Code Jam
algorithm;strings;haskell;complexity
w_s, short for welcome_solve, is, frankly, a poor name.  You're writing a function that counts the number of subsequences.  It's not even restricted to operating on strings.  Why not call it countSubsequences?countSubsequences :: Eq a => [a] -> [a] -> IntYour base cases should be simpler.countSubsequences [] _ = 1countSubsequences _ [] = 0The recursive case is correct, but could be written more clearly with a more idiomatic convention for parameter names, and using guard clauses.countSubsequences needle@(n:ns) haystack@(h:hs)  | n == h    = countSubsequences needle hs + countSubsequences ns hs  | otherwise = countSubsequences needle hs