Strings, Bits & Number Theory

String matching: the naive algorithm

The string matching problem: find every position where a pattern p (length m) occurs in a text t (length n). The naive algorithm tries every alignment and compares character by character.

Worst case O(n·m): on aaaa…ab each alignment matches m − 1 characters before failing, and all that knowledge is thrown away when the window slides by one. In practice, str.find, in, and str.count use a highly tuned C implementation (a two-way / Boyer-Moore-Horspool hybrid), so always reach for them first. Learn the algorithms below for when you need what the built-ins do not offer: matching on lists or token streams, many patterns at once, or fingerprints for similarity search.

Knuth-Morris-Pratt: never re-read the text

KMP's insight: when a mismatch happens after matching p[:j], we already know the last j text characters. The longest proper prefix of p[:j] that is also a suffix of it tells us how much of the pattern is still matched after shifting. Precompute that for every j in the failure table (also called the prefix function), fail[j] = length of the longest proper prefix of p[:j+1] that is also its suffix.

Why it is linear. The text index i only moves forward. Each successful comparison increases k by one, and each fallback decreases it by at least one, so the total number of fallbacks is at most the total number of increases, which is at most n. Searching is O(n), building the table is O(m) by the same argument: O(n + m) total, O(m) extra space.

Rabin-Karp: matching by rolling hash

Rabin-Karp compares hashes of windows instead of characters. Treat a window as a number in base B modulo a large prime M: h = (c₀·B^(m-1) + c₁·B^(m-2) + … + c_(m-1)) mod M. Sliding the window one step is O(1): remove the leading character's contribution, multiply by B, add the new one.

h = ((h - ord(out_char) * B**(m-1)) * B + ord(in_char)) % M

Equal hashes might be a collision, so confirm with a direct comparison. With a random-ish large prime, collisions are rare and the expected time is O(n + m); the worst case (every window collides) is O(n·m). Its real strength is matching many patterns of the same length at once: put their hashes in a set.

Palindromes: expand around the center

A palindrome reads the same backwards. Checking one string is s == s[::-1]. Finding the longest palindromic substring naively checks O(n²) substrings at O(n) each. Better: every palindrome has a center, either a character (odd length) or a gap between two characters (even length). There are 2n − 1 centers; expand outwards from each while the ends match. O(n²) time, O(1) space, and very fast in practice.

Bit manipulation

An int is a sequence of bits. Python integers have unlimited width; negative numbers behave as if they had infinitely many leading 1s (two's complement). The operators: & (and), | (or), ^ (xor), ~ (not, ~x == -x - 1), << and >> (shifts). Explore them, and the IEEE-754 float layout, in the visualizer.

XOR tricks

XOR is its own inverse: a ^ a == 0 and a ^ 0 == a, and it is commutative and associative. So XOR-ing a list where every value appears twice except one leaves exactly the odd one out, in O(n) time and O(1) space. The same property powers RAID parity, simple checksums, and the one-time pad.

Subsets as bitmasks

A set drawn from n items can be stored as an n-bit integer: bit i is 1 when item i is in the set. Union is |, intersection &, difference a & ~b, membership a bit test, and the size is bit_count(). Iterating mask from 0 to 2ⁿ − 1 visits every subset, an iterative alternative to the backtracking in M33.

Bitmasks are also the state in bitmask DP (M32 + this section): the travelling salesman problem's Held-Karp algorithm uses dp[mask][last] = shortest path visiting exactly the cities in mask and ending at last, O(2ⁿ·n²) instead of O(n!).

Number theory: gcd, lcm, and Euclid

The greatest common divisor of a and b is the largest integer dividing both. Euclid's algorithm (about 300 BCE) rests on one fact: any common divisor of a and b also divides a % b, so gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a. Step through it:

Each two steps at least halve the larger argument, so Euclid runs in O(log min(a, b)) steps. The least common multiple follows: lcm(a, b) = a // gcd(a, b) * b (divide first to keep numbers small). In real code use math.gcd and math.lcm, which accept any number of arguments.

The extended Euclidean algorithm also finds integers x, y with a·x + b·y = gcd(a, b) (Bézout's identity), which is how modular inverses are computed.

Primes and the sieve of Eratosthenes

Trial division tests one number n in O(√n): if n has a factor larger than √n, it also has one smaller. To find all primes up to N, the sieve of Eratosthenes is far better: cross off multiples of each prime, starting at p² (smaller multiples were already crossed off by smaller primes). It runs in O(N log log N), which is almost linear.

Modular arithmetic and fast exponentiation

Arithmetic modulo m wraps around like a clock. Addition, subtraction, and multiplication commute with taking remainders: (a * b) % m == ((a % m) * (b % m)) % m. That lets you compute huge results (the number of ways mod 10⁹ + 7, a hash value) without ever building huge intermediate numbers.

Fast modular exponentiation (square and multiply) computes a^b mod m in O(log b) multiplications by reading b's bits: square the base at every step, and multiply it into the result when the current bit is 1. Python's three-argument pow(a, b, m) does exactly this in C.

Modular inverse. x is the inverse of a mod m when a·x % m == 1. It exists exactly when gcd(a, m) == 1. Since Python 3.8, pow(a, -1, m) computes it (raising ValueError when no inverse exists). For a prime m, Fermat's little theorem gives another route: pow(a, m - 2, m).

Hashing and a crypto teaser

Polynomial rolling hashes (Rabin-Karp) are modular arithmetic. So is the most famous public-key system, RSA. A toy version with tiny primes shows the whole idea in six lines; real RSA uses primes with hundreds of digits.

1. Pick primes p and q; let n = p·q and φ = (p − 1)(q − 1).
2. Pick e with gcd(e, φ) = 1 (65537 is standard); compute d = e⁻¹ mod φ.
3. Encrypt: c = m^e mod n. Decrypt: m = c^d mod n. This works by Euler's theorem.
4. Security rests on factoring: knowing n but not p and q, nobody can compute φ and therefore d.

Python 3.15 preview: math.integer

pixi exec --spec "python=3.15" python integer_demo.py

On Python 3.14, which this course targets, keep using math.isqrt, math.comb, math.perm, math.factorial, math.gcd, and math.lcm.

Practice

def find_all(text: str, pattern: str) -> list[int]:
    fail = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k and pattern[i] != pattern[k]:
            k = fail[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        fail[i] = k
    hits: list[int] = []
    k = 0
    for i, ch in enumerate(text):
        while k and ch != pattern[k]:
            k = fail[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - k + 1)
            k = fail[k - 1]
    return hits

def count_palindromes(s: str) -> int:
    total = 0
    for center in range(2 * len(s) - 1):
        lo = center // 2
        hi = lo + center % 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            total += 1
            lo -= 1
            hi += 1
    return total

from functools import reduce
from operator import xor

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

def single_number(nums: list[int]) -> int:
    return reduce(xor, nums, 0)

def hamming(a: int, b: int) -> int:
    return (a ^ b).bit_count()

import math

def smallest_factors(n: int) -> list[int]:
    spf = list(range(n + 1))
    for k in range(min(2, n + 1)):
        spf[k] = 0
    for p in range(2, math.isqrt(n) + 1):
        if spf[p] == p:
            for m in range(p * p, n + 1, p):
                if spf[m] == m:
                    spf[m] = p
    return spf

def factorize(k: int, spf: list[int]) -> list[int]:
    out: list[int] = []
    while k > 1:
        out.append(spf[k])
        k //= spf[k]
    return out

def mod_inverse(a: int, m: int) -> int:
    old_r, r = a % m, m
    old_s, s = 1, 0
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    if old_r != 1:
        raise ValueError(f"{a} has no inverse modulo {m}")
    return old_s % m

Mini-project

pixi init snippets && cd snippets
pixi add python pytest
pixi run python snippets.py essay_a.txt essay_b.txt --k 8
pixi run pytest -q

Quiz

Recap

• Naive matching is O(n·m); KMP is O(n + m) by never re-reading text; Rabin-Karp is expected O(n + m) using rolling hashes, and excels at many patterns.
• Expand-around-center finds palindromes in O(n²) time and O(1) space.
• Masks: test (x >> i) & 1, set |, clear & ~, toggle ^; x & (x - 1) drops the lowest set bit; bit_count() counts bits. Parenthesize bitwise expressions in comparisons.
• An n-bit integer is a subset of n items; loop over range(1 << n) to enumerate subsets.
• Euclid computes gcd in O(log n); the sieve finds primes up to N in O(N log log N).
• pow(a, b, m) is fast modular exponentiation; pow(a, -1, m) is the modular inverse; RSA is built from exactly these.

Going further

• int.bit_count and bit_length
• Built-in pow with a modulus
• math: number-theoretic functions
• PEP 791: math.integer
• secrets: generate secure random numbers
• Next: M35 Problem-Solving Patterns.