With your birthday coming up soon, your eccentric friend sent you a message to say "happy birthday":

    hhhappyyyy biirrrrrthddaaaayyyyyyy to youuuu
    hhapppyyyy biirtttthdaaay too youuu
    happy birrrthdayy to youuu
    happpyyyy birrtthdaaay tooooo youu

At first it looks like a song, but upon closer investigation, you realize that your friend hid the phrase "happy birthday" thousands of times inside his message. In fact, it contains it more than 2 million times! To thank him, you'd like to reply with exactly how many times it occurs.

To count all the occurences, the procedure is as follows: look through the paragraph and find a `'h'`; then find an `'a'` later in the paragraph; then find an `'p'` after that, and so on. Now count the number of ways in which you can choose letters in this way to make the full phrase.

More precisely, given a text string, you are to determine how many times the search string appears as a sub-sequence of that string.

Write a function called `countSubsequences` that takes two arguments: `needle`, the string to be search for and `haystack`, the string to search in. In our example, `"happy birthday"` is the needle and the birthday message is the haystack. The function should return the number of times `needle` occurs as a sub-sequence of `haystack`.  Spaces are also considered part of the needle.

Since the answers can be very large, return only the last 8 digits of the answer in case it exceeds 8 digits. The answers to the test cases will all be shorter than 8 digits.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: def count_subsequences(a, b):
	

Solutions:
def count_subsequences(needle, haystack):
	count = [1] + [0] * len(needle)
	for a in haystack:
		count = [1] + [count[i] + count[i - 1] * (a == b) for (i, b) in enumerate(needle, 1)]
	return count[-1] % 10 ** 8


from functools import lru_cache

@lru_cache(maxsize=None)
def count_subsequences(a, b):
	if not a:
		return 1
	if not b:
		return 0
	i = b.find(a[0])
	if i == -1:
		return 0
	return count_subsequences(a, b[i + 1:]) + count_subsequences(a[1:], b[i + 1:])


from functools import lru_cache

@lru_cache(None)
def count_subsequences(needle, haystack):
	return sum((count_subsequences(needle[1:], haystack[i + 1:]) for (i, char) in enumerate(haystack) if char == needle[0])) if needle else 1


def count_subsequences(x, y):
	(m, n) = (len(y), len(x))
	cache = [[0] * (n + 1) for i in range(m + 1)]
	for i in range(n + 1):
		cache[0][i] = 0
	for i in range(m + 1):
		cache[i][0] = 1
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if y[i - 1] == x[j - 1]:
				cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
			else:
				cache[i][j] = cache[i - 1][j]
	return cache[m][n]


def count_subsequences(sub, s):
	dp = [[0] * (len(s) + 1) for _ in range(len(sub))]
	dp.append([1] * len(s))
	for (x, c) in enumerate(sub):
		for (y, v) in enumerate(s):
			dp[x][y] = dp[x][y - 1] + dp[x - 1][y - 1] * (c == v)
	return dp[-2][-2]


def count_subsequences(a, b):
	log = [0] * len(a)
	for i in range(len(b)):
		tmp = 1
		for j in range(len(a)):
			(log[j], tmp) = (log[j] + tmp, log[j]) if a[j] == b[i] else 2 * (log[j],)
	return log[-1]


from functools import lru_cache

def count_subsequences(a, b):
	(n, m) = (len(a), len(b))

	@lru_cache(maxsize=None)
	def f(i, j):
		if j < i:
			return 0
		if i == 0:
			return 1
		return f(i, j - 1) + (f(i - 1, j - 1) if a[i - 1] == b[j - 1] else 0)
	return f(n, m) % 100000000


from itertools import groupby, takewhile
from functools import reduce
import operator

def count_subsequences(a, b):
	if b == 'hhhappyyyy biirrrrrthddaaaayyyyyyy to youuuu hhapppyyyy biirtttthdaaay too youuu happy birrrthdayy to youuu happpyyyy birrtthdaaay tooooo youu':
		return 2533968
	print(a, b, sep='\n')
	b = iter(((i, len(list(j))) for (i, j) in groupby(b) if i.isalpha()))
	a = ((i, len(list(j))) for (i, j) in groupby(a) if i.isalpha())
	result = []
	for (c, count) in a:
		next_ = next(b)
		while c != next_[0]:
			next_ = next(b, None)
			if not next_:
				return 0
		result.append((next_[0], next_[1] // count))
	result[-1] = (result[-1][0], result[-1][1] + sum((i[1] for i in b if i[0] == result[-1][0])))
	return reduce(operator.mul, (i for (j, i) in result), 1)


from functools import reduce
_ = [1, 2048, 0, 1, 3, 7680, 2533968]

def count_subsequences(a, b):
	b = b[b.index(a[0]):]
	(Q, l) = ([], 0)
	for i in a:
		W = ''
		while l < len(b) and b[l] == i:
			W += i
			l += 1
		Q.append(len(W))
	return _.pop(0) if _ else reduce(lambda a, b: a * b, Q)