The hidden motif

Problem

Irene is a composer, and she likes to hide her favorite motif inside her melodies: the notes of the motif show up in order, but with other notes in between. Now she wants to know in how many different ways the motif can be found in a melody.

Write a function that takes melody and motif, two strings made of the letters C, D, E, F, G, A and B, one letter per note. The melody has at most 14 notes and may be empty; the motif has at least one note. Return a whole number: in how many ways you can pick notes from the melody that, read in the order they appear, spell the motif. You can skip as many notes as you like, but you cannot reorder them. Two ways are different if they use at least one different position in the melody, even if the note is the same.

With "CEGCEG" and "CG": the C at position 0 pairs with each of the two Gs, and the C at position 3 only with the G at the end. It returns 3. With "CDEFG" and "GC", the only C comes before the G, so it returns 0.

Examples

• The motif shows up three times

  "CEGCEG", "CG" → 3

• The notes come in another order

  "CDEFG", "GC" → 0

• Repeated notes

  "CCC", "CC" → 3

• A single note

  "GAGAG", "G" → 3

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def ways(melody, motif):
    pass

function ways(melody, motif) {
}