Google Code jam puzzle - Welcome to Code Jam

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 [] = 0
w_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_xs

And here is the code to get the last 4 digits:

getLast4 (w:x:y:z: []) = [w,x,y,z]
getLast4 (x:xs) = getLast4 xs
format_solve problem 
         | solution < 1000 = getLast4 $ show $ 10000 + solution
         | otherwise  = getLast4 $ show solution
         where solution = w_s "welcome to code jam" problem

Example usage:

λ> format_solve "format_solve welcome to codejam"
"0000"
λ> format_solve "wweellccoommee to code qps jam"
"0256"
λ> format_solve "elcomew elcome to code jam"
"0001"

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] -> Int

Your base cases should be simpler.

countSubsequences [] _ = 1
countSubsequences _ [] = 0

The 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

StackExchange Code Review Q#77470, answer score: 3