Editable substring fingerprints: join hashes in a segment tree

Last updated: 5 Oct 20269 min read

tutorial

An editable substring fingerprint index stores a polynomial hash and character length for each segment-tree node. To join adjacent spans, multiply the left hash by a base raised to the right span length, then add the right hash modulo a fixed prime. This positional rule lets a query combine its covered nodes into a normalized fingerprint independent of where the substring begins. A point replacement rebuilds only the leaf-to-root path. The example maintains two modular hashes and checks equal lengths, making accidental agreement less likely than one hash but never impossible. A matching fingerprint is a candidate for equality, not a proof; a caller needing exact equality must compare the underlying characters after the hash test. Text length is fixed, and offsets count Unicode code points, not grapheme clusters.

Operational case

The text dock47dock47 has two equal six-character halves and two equal four-character dock prefixes. Replacing the final 7 with 9 makes the six-character halves unequal; restoring 7 makes them match again. An empty span has length zero and zero hashes, while a requested span beyond the text boundary raises an error. The same hashes cannot identify which edit occurred or where it occurred. For security decisions, stored hash pairs alone are insufficient evidence of exact content identity, since distinct strings can collide under finite moduli.

Working Python program

class AlertTextFingerprint:
    BASE = 911382323
    MODULI = (1000000007, 1000000009)

    def __init__(self, alert_text):
        if not alert_text:
            raise ValueError("at least one character is required")
        self.length = len(alert_text)
        self.powers = [[1] * (self.length + 1) for _ in self.MODULI]
        for number, modulus in enumerate(self.MODULI):
            for count in range(1, self.length + 1):
                self.powers[number][count] = self.powers[number][count - 1] * self.BASE % modulus
        self.tree = [None] * (4 * self.length)

        def build(node, low, high):
            if high - low == 1:
                encoded = ord(alert_text[low]) + 1
                self.tree[node] = (1, encoded % self.MODULI[0], encoded % self.MODULI[1])
                return
            middle = (low + high) // 2
            build(node * 2, low, middle)
            build(node * 2 + 1, middle, high)
            self.tree[node] = self._join(self.tree[node * 2], self.tree[node * 2 + 1])

        build(1, 0, self.length)

    def _join(self, left, right):
        if left is None:
            return right
        if right is None:
            return left
        return (left[0] + right[0],
                (left[1] * self.powers[0][right[0]] + right[1]) % self.MODULI[0],
                (left[2] * self.powers[1][right[0]] + right[2]) % self.MODULI[1])

    def replace(self, position, character):
        if not 0 <= position < self.length or len(character) != 1:
            raise ValueError("one in-range character required")

        def change(node, low, high):
            if high - low == 1:
                encoded = ord(character) + 1
                self.tree[node] = (1, encoded % self.MODULI[0], encoded % self.MODULI[1])
                return
            middle = (low + high) // 2
            if position < middle:
                change(node * 2, low, middle)
            else:
                change(node * 2 + 1, middle, high)
            self.tree[node] = self._join(self.tree[node * 2], self.tree[node * 2 + 1])

        change(1, 0, self.length)

    def fingerprint(self, left, right):
        if not 0 <= left <= right <= self.length:
            raise IndexError("invalid text interval")

        def read(node, low, high):
            if right <= low or high <= left:
                return None
            if left <= low and high <= right:
                return self.tree[node]
            middle = (low + high) // 2
            return self._join(read(node * 2, low, middle), read(node * 2 + 1, middle, high))

        return read(1, 0, self.length) or (0, 0, 0)

    def possibly_equal(self, first, second, width):
        if width < 0:
            raise ValueError("negative width")
        return self.fingerprint(first, first + width) == self.fingerprint(second, second + width)


alert_text = AlertTextFingerprint("dock47dock47")
print(alert_text.possibly_equal(0, 6, 6), alert_text.possibly_equal(0, 6, 4))
alert_text.replace(11, "9")
print(alert_text.possibly_equal(0, 6, 6))
alert_text.replace(11, "7")
print(alert_text.possibly_equal(0, 6, 6))

Output

True True
False
True

Time, space, and tradeoff

For N characters, building powers and tree summaries costs O(N) time and space. A point replacement or range fingerprint touches O(log N) nodes and uses O(log N) recursion stack space. Comparing two hashes costs O(log N), while verifying a matching pair against the actual text takes O(length) further time. The example does not retain an editable source string, so an exact verification layer must hold one separately. Hashing is useful for quickly rejecting unequal spans under frequent edits; it should not be described as a collision-free index or cryptographic integrity check.

Common Mistakes

Do not compare hashes of different lengths as if they represented equal strings.
Do not omit the right-span power when joining two child hashes.
Do not treat matching modular fingerprints as guaranteed equality.
Do not promise insertion or deletion when the index only replaces characters.

Connected lessons

Compare this operation boundary with Successor disjoint sets: skip permanently retired slots, Persistent range-distinct counts: keep only the latest position active, Sliding medians: expire heap entries by event identity, Ball trees: prune exact nearest-depot search with radius bounds, then complete the audit project and decision quiz.

data structures

range-query-structures