Tremor signature

A seismograph writes one letter a minute for years. When a foreshock signature is published, the tape has to be searched for it once, forward, without backing up.

The problem

A station's drum recorder condenses each minute of ground motion to one letter: q for quiet, m for a micro-tremor, j for a jolt. Decades of tape are on file as a single string, one character per minute.

Seismologists publish a signature: a short string of the same letters that precedes a particular kind of event. Report the earliest minute at which the signature begins on the tape — the index where it appears as a contiguous run — or -1 if it never does. An empty signature begins at minute 0.

With only three letters, near-misses are constant: a five-letter signature matches four of them at dozens of positions before the real occurrence.

Input. tape — one character per minute. signature — the string sought.

Output. The index of its first occurrence, or -1.

Example.

tape = 'qqmqmqmjqmqmj', signature = 'qmqmj'   ->  3

The signature almost lands at minute 1: qmqm matches, then the tape has q where the signature wants j. It lands properly at minute 3.

A second example, where the near-misses stack up:

tape = 'mmmmmmmmmj', signature = 'mmmj'   ->  6

Six failed alignments, each matching three letters first — and a restarting method reads those letters again every time.

Constraints.

• 0 <= len(tape) <= 10^6
• 0 <= len(signature) <= 10^4
• both strings use the letters q, m, j

Hints

Approach

Brute force

Line the signature up at every minute and compare until it fails: up to n · m comparisons, which at n = 10⁶ and m = 10⁴ is 10¹⁰ — minutes of work. The mmmmmmmmmj example is the shape that provokes it, every alignment matching almost all the way before dying.

The insight

On a mismatch after matched letters, the tape pointer never has to move backwards: the longest proper prefix of the signature that is also a suffix of those matched letters is already matched, so the search resumes there.

The precondition is that the fallback length depends on the signature alone. The letters just matched are the signature's first matched letters, so which of them can serve as a fresh start is a question about the signature, answerable before the tape is opened. Build border[i] — the longest proper prefix of signature[:i+1] that is also its suffix — and every mismatch is one lookup.

Algorithm

1. Return 0 for an empty signature, -1 if it is longer than the tape.
2. Build border by running the same fallback rule with the signature as its own tape.
3. Walk the tape once, carrying matched, initially 0.
4. While matched is non-zero and the reading differs from signature[matched], set matched = border[matched - 1].
5. If the reading equals signature[matched], increment matched.
6. When matched reaches the signature's length, return minute - matched + 1.
7. If the tape runs out, return -1.

Complexity

Time O(n + m): the tape index only increases, and matched rises at most once per minute, so it can fall at most n times in total — the fallback loop runs O(n) times across the whole search, not per minute. The table costs O(m) by the same argument. Space O(m).

Solution

"""Tremor signature — first occurrence on the tape via the KMP fallback table."""


def border_table(signature):
    """table[i] = length of the longest proper prefix of signature[:i+1] that is
    also a suffix of it. Built by matching the signature against itself."""
    table = [0] * len(signature)
    span = 0
    for i in range(1, len(signature)):
        # invariant: span is the length of the best border of signature[:i]
        while span and signature[i] != signature[span]:
            span = table[span - 1]
        if signature[i] == signature[span]:
            span += 1
        table[i] = span
    return table


def solve(tape, signature):
    if not signature:
        return 0
    if len(signature) > len(tape):
        return -1

    table = border_table(signature)
    matched = 0
    for minute, reading in enumerate(tape):
        # invariant: signature[:matched] is a suffix of tape[:minute]
        while matched and reading != signature[matched]:
            matched = table[matched - 1]      # keep the border, discard the rest
        if reading == signature[matched]:
            matched += 1
        if matched == len(signature):
            return minute - matched + 1
    return -1

TESTS = [
    (("qqmqmqmjqmqmj", "qmqmj"), 3),
    (("mmmmmmmmmj", "mmmj"), 6),
    (("qqqqqq", "qqj"), -1),
    (("qmj", ""), 0),
    (("qmj", "qmj"), 0),
    (("qm", "qmj"), -1),
    (("", "j"), -1),
    (("jjjj", "jj"), 0),
    (("qmqmqmqmj", "qmqmj"), 4),
]

Pitfalls

• Setting matched = 0 on a mismatch. Small tests still pass and the table is still built, but progress is discarded and the run time returns to O(n · m) — the cost the table exists to remove.
• Dropping proper from the table's definition. If the whole prefix counts as its own suffix, border[i] is always i + 1, every fallback is a no-op, and the search hangs on the first mismatch.
• Reporting minute rather than minute - len(signature) + 1. That is where the signature ends: 7 instead of 3 on the first example. An empty signature also needs its own answer of 0, or the search falls through to -1.

Variants

• Motif on the roll — same first-occurrence question, answered with prefix-match lengths instead of a fallback table.
• KMP and the failure function — the lesson behind the table and its amortised bound.