Motif in the weave

A weaving mill keeps a colour card for every bolt: one letter per weft pick, in the order the shuttle laid them. The design office wants to know how often a motif hides inside a card — not whether, but how many ways.

The problem

The card is a string, card, one lowercase letter per pick: r for red, b for blue, g for green. A motif is a shorter string of the same letters.

A motif appears in a card whenever you can choose a set of picks, reading left to right, whose colours spell the motif. The chosen picks need not be adjacent — the design office is looking for the motif at any spacing, since a weaver can slow the pattern down across the bolt. Two appearances are different when the chosen picks are different, even if the colours read the same.

Count the appearances, modulo 1000000007.

Input. card — a string of colour letters. motif — a shorter string of colour letters.

Output. The number of ways to choose picks spelling the motif, modulo 1000000007.

Example.

card = "rrbrrb", motif = "rb"   ->  6

The blue at index 2 can be paired with either red before it: 2 ways. The blue at index 5 has four reds before it: 4 more. Six in total, though the card contains only two blues.

A second example, where the same letter repeats:

card = "bbb", motif = "bb"   ->  3

Three ways to pick two of the three blue picks. The colours read identically in all three, but the picks differ, so they count separately — this is the case that breaks any solution counting distinct strings.

Constraints.

• 1 <= len(card) <= 1000
• 1 <= len(motif) <= 100
• Both strings use lowercase letters only
• The answer is reported modulo 1000000007

Hints

Approach

Brute force

Enumerate every set of len(motif) picks and check whether it spells the motif. That is len(card) choose len(motif) sets — a 145-digit number at the top of the range. The take-or-skip recursion is no better on its own: 2 to the power of 1000 leaves, and it re-solves the same suffix pair over and over.

The insight

The number of ways depends only on how much of the card and how much of the motif remain, so one table entry per pair of prefixes replaces the whole recursion.

Write ways[i][j] for the number of ways to spell the first j letters of the motif using the first i picks of the card. The last pick is either skipped, contributing ways[i-1][j], or used, contributing ways[i-1][j-1] — and only when its colour matches motif[j-1]. The two cases are disjoint, because a pick is in the chosen set or it is not, so the counts add rather than overlap.

The boundary row is where the counting is won or lost. ways[i][0] is 1 for every i: there is exactly one way to spell nothing, namely by skipping every pick. ways[0][j] is 0 for j above zero: no picks cannot spell a letter.

Only the previous row is ever read, so the table rolls down to a single array of len(motif) + 1 counts — provided the inner loop runs from the end of the motif backwards, so that each entry still sees the previous row's value.

Algorithm

1. Make ways, of length len(motif) + 1, set to 0 except ways[0] = 1.
2. For each pick colour c in the card, left to right:
3. For j from len(motif) down to 1: if motif[j-1] == c, add ways[j-1] into ways[j], modulo 1000000007.
4. Return the last entry.

Complexity

Time O(n * m) — 100000 additions at the top of the range, one per (pick, motif position) pair. Space O(m), a single rolled row.

Solution

"""Motif in the weave — counting subsequences with a rolled two-index table."""

MOD = 1000000007


def solve(card, motif):
    # ways[j] = number of ways to spell motif[:j] out of the picks seen so far.
    # ways[0] stays 1 for every prefix: skipping everything spells nothing, once.
    ways = [0] * (len(motif) + 1)
    ways[0] = 1
    for colour in card:
        # Downward, so ways[j - 1] is still the count from BEFORE this pick —
        # one pick can never spell two motif letters.
        for j in range(len(motif), 0, -1):
            if motif[j - 1] == colour:
                ways[j] = (ways[j] + ways[j - 1]) % MOD
    return ways[len(motif)]

TESTS = [
    (("rrbrrb", "rb"), 6),
    (("bbb", "bb"), 3),
    (("bb", "bb"), 1),          # forward inner loop would report 3 here
    (("gbg", "bb"), 0),
    (("r", "r"), 1),
    (("rb", "br"), 0),          # order of the picks is fixed by the card
    (("b" * 40, "b" * 20), 846527861),   # 40 choose 20, past the modulus
]

Pitfalls

• Running the inner loop forwards. Then ways[j-1] has already absorbed the current pick, so one pick spells two motif letters at once. On card = "bb", motif = "bb" that reports 3 instead of 1. Counting downward is what keeps the read on the previous row.
• Zeroing ways[0] after the first pick. The empty motif stays reachable from every prefix by skipping everything, so that entry is 1 forever. Clear it and the whole answer collapses to 0.
• Counting distinct spelled strings instead of distinct pick sets. The "bbb" example is 3, not 1. Deduplicating by colour is a different question and gives a smaller number on every card with a repeated colour.
• Taking the modulus only at the end. The true count for a 1000-pick card can run to 140 digits; in a fixed-width integer that silently wraps. Reduce on every addition.

Variants

• Readings of the frieze — the same consume-a-prefix table, listing the reconstructions instead of counting them.
• One struck reading — one index rather than two, when the state is a flag rather than a position.