Motif on the roll

A print roll comes off the press as one long strip of cells. The cutter has to be told the first cell where the ordered motif begins, and the roll is too long to read twice.

The problem

A wallpaper press prints one cell at a time onto a continuous roll. A scanner records the finished roll as a string, one letter per cell: f fern, d dot, v vine, s stripe.

An order names a motif — a short run of cells — and asks for the roll to be cut where it first appears. Report the index of the cell at which the motif starts its first occurrence, or -1 if the roll never prints it. An empty motif starts at cell 0.

The press repeats a few letters endlessly, so the roll is the hostile kind of input: the motif agrees for most of its length at many cells before it agrees for all of it.

Input. strip — the scanned roll, one character per cell. motif — the run of cells being looked for.

Output. The index of the first cell of the first occurrence, or -1.

Example.

strip = 'fdfdvfdfdf', motif = 'fdfdf'   ->  5

The motif agrees with the roll for four cells starting at cell 0, then the roll prints v where the motif wants f. Its real occurrence starts at cell 5 and runs to the end.

A second example, on a roll that is almost one letter:

strip = 'vvvvvvvvvd', motif = 'vvd'   ->  7

Seven starts agree for two cells before failing. Only the eighth agrees for three.

Constraints.

• 0 <= len(strip) <= 10^6
• 0 <= len(motif) <= 10^5
• both use the letters f, d, v, s

Hints

Approach

Brute force

Align the motif at every cell and compare until it fails: up to n · m character comparisons, and with a four-letter alphabet the failures come late. At n = 10⁶ and m = 10⁵ that is 10¹¹ comparisons — hours.

The insight

Join the motif to the roll and, for every position, measure how far the string from there agrees with the string's own start; a position whose measure equals the motif's length is an occurrence, and the measures cost one pass in total.

The measures are cheap because of one bookkeeping fact: the algorithm remembers the rightmost stretch [lo, hi) already known to agree with the start. A position i inside it sits at a known offset, so its measure begins as a copy of the measure at i - lo, capped by hi - i. Every actual character comparison either fails once for that position or pushes hi further right, and hi never moves back — so comparisons across the whole run are bounded by the joined length.

Algorithm

1. Return 0 for an empty motif, -1 if the motif is longer than the roll.
2. Build joined = motif + '|' + strip, where | is never printed.
3. Set every measure to 0 and keep a window lo = hi = 0.
4. For each position i from 1: if i < hi, start its measure at min(hi - i, measure[i - lo]).
5. Extend the measure by comparing forward while the characters match.
6. If i + measure[i] passes hi, move the window to [i, i + measure[i]).
7. Return the first i past the separator with measure[i] == len(motif), mapped back to a cell as i - len(motif) - 1. If none, return -1.

Complexity

Time O(n + m) — each comparison either ends one position's extension or advances hi, which only moves right. Space O(n + m) for the joined string and its measures, the price paid over a fallback table's O(m).

Solution

"""Motif on the roll — first occurrence from prefix-match lengths on motif + roll."""


def prefix_reach(text):
    """reach[i] = how many characters from position i match the start of text."""
    n = len(text)
    reach = [0] * n
    if n:
        reach[0] = n
    lo = hi = 0
    for i in range(1, n):
        # invariant: [lo, hi) is the rightmost stretch known to match the start
        if i < hi:
            reach[i] = min(hi - i, reach[i - lo])   # the cap is what keeps it honest
        while i + reach[i] < n and text[reach[i]] == text[i + reach[i]]:
            reach[i] += 1
        if i + reach[i] > hi:
            lo, hi = i, i + reach[i]
    return reach


def solve(strip, motif):
    span = len(motif)
    if span == 0:
        return 0
    if span > len(strip):
        return -1

    # '|' is never printed, so no measure can run out of the motif into the roll.
    joined = motif + "|" + strip
    reach = prefix_reach(joined)
    for i in range(span + 1, len(joined)):
        if reach[i] == span:
            return i - span - 1
    return -1

TESTS = [
    (("fdfdvfdfdf", "fdfdf"), 5),
    (("vvvvvvvvvd", "vvd"), 7),
    (("ffff", "fv"), -1),
    (("fff", "ff"), 0),
    (("vvd", "vvv"), -1),
    (("dvfs", ""), 0),
    (("dvfs", "dvfs"), 0),
    (("dv", "dvf"), -1),
    (("", "f"), -1),
    (("dddd", "dd"), 0),
]

Pitfalls

• Leaving out the separator. With joined = motif + strip, a measure taken inside the motif can reach the motif's own length. Searching fff for ff then reports cell 1 instead of cell 0.
• Copying the measure without the cap. Dropping min(hi - i, ...) claims agreement past the end of the known stretch, which asserts characters nobody compared. Searching vvd for vvv then returns cell 1 for a motif that is not on the roll at all.
• Forgetting the separator in the index arithmetic. The cell is i - len(motif) - 1; subtracting only the motif length reports 6 instead of 5 on the first example.

Variants

• Tremor signature — the same first occurrence, found with a fallback table in O(m) extra space instead of O(n + m).
• The permissions desk — a whole set of equal-width motifs at once, and every occurrence rather than the first.