String matching, hashing, and palindrome · HTML
H[i+1]=(H[i]base+code(s[i])) mod M; hash(l,r)=H[r]-H[l]base^(r-l) mod M.
Recognition signals
- Many substring-equality checks
- Fixed-length window lookup
- Binary search over duplicate length
- Repeated character comparison is too costly
- Collision verification or double hashing is acceptable
False friends
| Signal | Why it is different |
|---|
| No probabilistic error is tolerable | A single hash can collide; verify candidates, double-hash, or use a deterministic algorithm. |
| Approximate textual similarity | Hashing tests exact equality, not edit distance. |
Core invariant
A prefix hash is a left-to-right polynomial; after power alignment, equal substrings have equal fingerprints.
State, transition, and processing order
| Item | Definition |
|---|
| State | Prefix hashes, powers of base, and modulus; high-reliability uses two independent parameter sets. |
| Transition | Append one character to extend the prefix; extract a range by subtracting and power-aligning two prefixes. |
| Frontier / order | Preprocessing advances one character at a time; later window checks move endpoints without rescanning interiors. |
Python skeleton
class RollingHash:
def __init__(self, s, base=911382323, mod=1_000_000_007):
self.base, self.mod = base, mod
self.h = [0] * (len(s)+1)
self.p = [1] * (len(s)+1)
for i, ch in enumerate(s):
self.h[i+1] = (self.h[i]*base + ord(ch)+1) % mod
self.p[i+1] = self.p[i]*base % mod
def get(self, left, right):
return (self.h[right] - self.h[left]*self.p[right-left]) % self.mod
def probably_equal_substrings(s, a, b, length):
rh = RollingHash(s)
return rh.get(a,a+length) == rh.get(b,b+length)
Correctness sketch
- The prefix recurrence is exactly a polynomial in character codes.
- Subtracting the scaled left prefix leaves only coefficients in [l,r).
- Equal strings have equal coefficient sequences and therefore equal hashes.
- The converse is probabilistic; a second hash or direct verification controls collisions.
Complexity
| Time | Space | Parameters |
|---|
| O(n) preprocessing and O(1) per substring hash | O(n) | string length n; collision risk depends on base, modulus, and number of hashes |
Edge cases
- All empty substrings should hash equally
- Normalize modular subtraction
- Choose reasonable independent parameters
- Compared objects must share parameters
- Normalize Unicode consistently
Error patterns
| Pattern | Why it fails / fix |
|---|
| No power alignment | Raw prefix subtraction leaves position-dependent weights. |
| Treating equality as proof | A collision remains unless candidates are verified. |
| Mismatched parameters | Hashes using different base or modulus are incomparable. |
Selection and exclusion rules
- Many substring comparisons: rolling hash.
- One pattern, deterministic worst-case linear time: KMP.
- Before binary-searching length, prove the predicate is monotone.
- For commercially critical outputs, double-hash and verify source text.
| Relation | Template | Boundary |
|---|
| alternative | Trie prefix search | The task compares many fixed-length substrings rather than navigating prefixes. |
Original micro-example
| Part | Detail |
|---|
| Result | Both hashes match and both substrings are cab. |
| Scenario | Compare [0,3) and [3,6) in cabcab. |
| Walkthrough | Subtracting and aligning the second range yields the same coefficient sequence as the first. |
Recall prompts
My notes