Ways to Read a Pattern Inside a Text

A cryptographer counts the number of ways a short pattern can be read inside a longer text by deleting characters from text without reordering the rest. Two ways are different when they use different positions of text. Write embeddings(text, pattern) returning that count.

Examples

Input:  text = "banana", pattern = "ana"
Output: 4
Explanation: using positions (1,2,3), (1,2,5), (1,4,5) and (3,4,5).

Input:  text = "abc", pattern = ""
Output: 1

Input:  text = "ab", pattern = "ba"
Output: 0

Constraints

• 0 <= len(text) <= 800, 0 <= len(pattern) <= 10, lowercase letters.
• A memoised recursion needs at most len(text) + 1 stack levels.

Goals

• Recurse on two positions, one into each string
• Distinguish 'use this character' from 'skip it' branches
• Memoise the (i, j) pair to avoid exponential blow-up