The permissions desk

A submitted manuscript strips to two hundred thousand letters, and the extract bank holds ten thousand entries. One pass per entry is ten thousand passes; the budget is one.

The problem

A publisher's permissions desk screens each submission against text the house has already licensed. Case, spacing and punctuation go first, leaving one string of lowercase letters, manuscript.

The bank holds extracts worth clearing — lyrics, epigraphs, a rival's paragraph — cut by an indexer into stretches of one fixed length, so all extracts share a letter count. The merge of three imprints left duplicates.

Report every offset at which some banked extract begins — once per offset, even where two extracts start there or extracts overlap.

Input. manuscript, a string of lowercase letters, and bank, a list of equal-length strings.

Output. The start offsets, ascending.

Example.

manuscript = "starstarstart", bank = ["star", "tart"]   ->  [0, 4, 8, 9]

star sits at offsets 0, 4 and 8; tart starts at 9, one letter into that last star. Offset 1 holds tars, banked nowhere.

A second example, with overlaps and with no start:

manuscript = "eeeee", bank = ["eee"]    ->  [0, 1, 2]
manuscript = "sta",   bank = ["star"]   ->  []

Five e's hold three overlapping runs; an overlap is still a start. An extract longer than the manuscript begins nowhere.

Constraints.

• 1 <= len(manuscript) <= 2 * 10^5
• 1 <= len(bank) <= 10^4
• 1 <= L <= 10^3, the shared extract length
• all characters are lowercase letters

Hints

Approach

Brute force

Compare each of the n - L + 1 windows against every extract: O(n · k · L), which at n = 2·10⁵, k = 10⁴, L = 10³ is 2·10¹² letter comparisons. One linear-time search per extract still reads the manuscript k times.

The insight

Every extract is the same width, so one number per window tests the whole bank at once.

Hash the bank into buckets once, then slide a window of that width carrying its polynomial hash: drop the leaving letter, append the arriving one, O(1) a window instead of O(L). Equal widths are the precondition: mixed lengths leave nothing to roll. The hash is never proof, so a bucket hit is checked letter by letter.

Algorithm

1. Return [] if the extract length L exceeds len(manuscript).
2. Hash every extract into a dict from hash to the extracts carrying it.
3. Hash manuscript[:L] and precompute BASE^(L-1) mod M, the leaving letter's weight.
4. At each offset, if the hash is a key, compare the slice against that bucket, recording the offset on a match.
5. Roll: subtract the leaving letter times its weight, multiply by BASE, add the arriving one, mod M.

Complexity

Time O(n + k · L + occ · L) expected: a roll per offset, a hash per bank entry, an L-letter comparison per reported start. Space O(k · L) for the buckets. The third term bites: 'e' * 2·10⁵ against ['e' * 10³], the second example at full size, verifies all 199,001 windows — 2·10⁸ comparisons. Expected covers the other case: windows chosen to collide are compared for nothing. Aho-Corasick — a trie over the bank with failure links — has neither case: worst-case O(n + k · L + occ).

Solution

"""The permissions desk — one rolling hash slid along the manuscript."""

BASE = 257
MOD = (1 << 61) - 1


def extract_hash(text):
    """Polynomial hash, most significant letter first."""
    value = 0
    for letter in text:
        value = (value * BASE + ord(letter)) % MOD
    return value


def solve(manuscript, bank):
    if not bank:
        return []
    width = len(bank[0])
    if width == 0 or width > len(manuscript):
        return []

    # A shared hash proves nothing, so each bucket keeps the extracts themselves
    # for verification. Duplicated bank entries collapse into the set.
    buckets = {}
    for extract in bank:
        buckets.setdefault(extract_hash(extract), set()).add(extract)

    top = pow(BASE, width - 1, MOD)      # weight of the letter leaving the window
    window = extract_hash(manuscript[:width])

    starts = []
    for start in range(len(manuscript) - width + 1):
        # invariant: window == extract_hash(manuscript[start:start + width])
        bucket = buckets.get(window)
        if bucket is not None and manuscript[start:start + width] in bucket:
            starts.append(start)
        if start + width < len(manuscript):
            window = (window - ord(manuscript[start]) * top) % MOD
            window = (window * BASE + ord(manuscript[start + width])) % MOD
    return starts

TESTS = [
    (("starstarstart", ["star", "tart"]), [0, 4, 8, 9]),
    (("eeeee", ["eee"]), [0, 1, 2]),
    (("sta", ["star"]), []),
    (("starstar", ["star", "star"]), [0, 4]),      # banked twice, reported once
    (("eeeeeeeeee", ["eeee"]), [0, 1, 2, 3, 4, 5, 6]),
    (("ab", ["a", "b"]), [0, 1]),                  # width 1: every offset rolls
    (("star", ["star"]), [0]),
    (("stare", ["tare", "star"]), [0, 1]),         # two extracts, overlapping starts
    (("eeee", ["sta", "tar"]), []),
]

Pitfalls

• Slicing at every offset. manuscript[i:i+L] in extracts copies L letters per offset, handing back the O(n · L) you were avoiding. Slice after a bucket hit, never before.
• Trusting the hash. A start recorded on hash equality alone reports an extract nobody quoted — invisible until the first real submission.
• Rolling without the top weight. Subtracting ord(leaving) instead of ord(leaving) * BASE^(L-1) corrupts every window after the first: offset 0 is reported and nothing else.

Variants

• Tremor signature — one pattern rather than a set, in worst-case linear time from a failure function.
• Motif on the roll — one pattern again, first occurrence only.