In this Kata, you will count the number of times the first string occurs in the second. 

```Haskell
solve("zaz","zazapulz") = 4 because they are ZAZapulz, ZAzapulZ, ZazApulZ, zaZApulZ
```

More examples in test cases. 

Good luck!

Please also try [Simple time difference](https://www.codewars.com/kata/5b76a34ff71e5de9db0000f2)

Difficulty: introductory

Starter code:

def solve(a, b):
	

Solutions:
def solve(a, b):
    if len(a) is 1:
        return b.count(a)
    index = [x for x in range(len(b)-1) if b[x] is a[0]]
    return sum(solve(a[1:], b[x+1:]) for x in index)

def solve(a, b, i=0, j=0):
    return i == len(a) or sum(solve(a,b,i+1,x+1) for x in range(j, len(b)-(len(a)-i-1)) if a[i] == b[x])

from functools import lru_cache

def solve(a, b):
    l_a, l_b, rec = len(a), len(b), lru_cache(maxsize=None)(lambda x,y: (x == l_a) or sum(rec(x+1, i+1) for i in range(y, l_b) if b[i] == a[x]))
    return rec(0, 0)

def solve(a, b):
    if not a:
        return 1
    if not b:
        return 0
    if b[0].lower() == a[0].lower():
        return solve(a, b[1:]) + solve(a[1:], b[1:])
    else:
        return solve(a, b[1:])

def solve(a, b):
    if a[0] in b:
        if len(a) > 1:
            return solve(a[1:],b[b.index(a[0])+1:])+solve(a,b[b.index(a[0])+1:])
        else:
            print((b.count(a)))
            return b.count(a)
    else:
        return 0

    


def solve(a, b, i=0, j=0):
    return (1 if i == len(a) else
            0 if j == len(b) else
            solve(a,b,i,j+1) if a[i] != b[j] else
            solve(a,b,i+1,j+1) + solve(a,b,i,j+1))

def solve_dp (needle, haystack):
    # let prefixes[h][n] = number of n-letters-long prefixes
    #                      ending in h-th position of haystack
    N, H = len(needle), len(haystack)
    prefixes = [[1] + N*[0] for h in range(H)]
    
    def match (h, n): return haystack[h] == needle[n-1]
    prefixes[0][1] = 1 if match(0, 1) else 0

    for h in range(1, H):
        max_prefix_len = min(h+1, N)
        for n in range(1, max_prefix_len+1):
            with_current = prefixes[h-1][n-1] if match(h, n) else 0
            without_current = prefixes[h-1][n]
            prefixes[h][n] = with_current + without_current
    return prefixes[H-1][N]

def solve_recursive (needle, haystack):
    if not needle or needle == haystack: return 1
    if not haystack: return 0
    
    needle_head, *needle_tail = needle
    haystack_head, *haystack_tail = haystack
    match = needle_head == haystack_head
    
    head_matches = solve_recursive(needle_tail, haystack_tail) if match else 0
    tail_matches = solve_recursive(needle, haystack_tail)
    return head_matches + tail_matches

def solve (needle, haystack, method=solve_dp):
    return method(needle, haystack)



from itertools import combinations as c

def solve(a, b):
    tot=0
    a = tuple(a)
    b = [i for i in b if i in a]
    for k in range(len(b)):
        if b[k]!=a[0]: continue
        for kk in range(k+1, len(b)):
            if b[kk]!=a[1]: continue
            for i in c(b[kk+1:],len(a)-2):
                if i==a[2:]:
                    tot+=1
    return tot

def solve(a, b):
    if len(a)==1:
        return b.count(a)
    r=0
    for i in range(len(b)-len(a)+1):
        if b[i]==a[0]:
            r+=solve(a[1:],b[i+1:])
    return r

def solve(a,b):
    if not a: return 1
    x,c = a[0],0   
    for i in range(len(b)):
        if b[i] == x:
            c += solve(a[1:],b[i+1:])   
    return c