Union-Find, String and Bit Algorithms

This chapter covers union-find (disjoint sets), key string algorithms, and bit-level algorithms.

Why This Matters

Union-find solves dynamic connectivity (Kruskal's MST, connected components, percolation). String algorithms underpin parsing, search, and text processing. Bit algorithms are the fastest primitive operations and are essential in embedded and performance code.

Prerequisites

• c.alg.2 — recursion/DP (for some string algorithms).
• c.ops.bitwise — bit operators.

Core Concept

Union-find

Maintains a partition of elements into disjoint sets with near-O(1) find (which set?) and union (merge two sets), using parent pointers, union by rank/size, and path compression.

typedef struct {
    int *parent;
    int *rank;
    int n;
} UF;

int uf_find(UF *uf, int x)
{
    if (uf->parent[x] != x)
        uf->parent[x] = uf_find(uf, uf->parent[x]);  /* path compression */
    return uf->parent[x];
}

void uf_union(UF *uf, int a, int b)
{
    int ra = uf_find(uf, a), rb = uf_find(uf, b);
    if (ra == rb) return;
    if (uf->rank[ra] < uf->rank[rb]) { uf->parent[ra] = rb; }
    else if (uf->rank[ra] > uf->rank[rb]) { uf->parent[rb] = ra; }
    else { uf->parent[rb] = ra; uf->rank[ra]++; }
}

String algorithms

• Pattern matching: naive O(n·m), Knuth-Morris-Pratt O(n+m), Boyer-Moore.
• String hashing (Rabin-Karp): rolling hash for fast matching.
• Longest common prefix / suffix arrays: for advanced text processing.

Bit algorithms

• Population count (__builtin_popcount).
• Count leading/trailing zeros (__builtin_clz/__builtin_ctz).
• Isolate lowest set bit: x & -x.
• Clear lowest set bit: x & (x - 1).
• Reverse bits, count set bits, bit permutations.

Examples

Clear lowest set bit (fast popcount loop)

int popcount(unsigned int x)
{
    int c = 0;
    while (x) {
        x &= (x - 1);   /* clear lowest set bit */
        c++;
    }
    return c;
}

KMP prefix function

void kmp_prefix(const char *pat, int m, int *pi)
{
    pi[0] = 0;
    for (int i = 1; i < m; i++) {
        int k = pi[i - 1];
        while (k > 0 && pat[i] != pat[k]) k = pi[k - 1];
        if (pat[i] == pat[k]) k++;
        pi[i] = k;
    }
}

How It Works

Union-find uses a forest of trees; path compression flattens them, and union by rank keeps them shallow, giving near-constant amortized time. KMP precomputes the longest proper border to avoid re-scanning. Bit algorithms exploit the CPU's native bit operations.

Variations

Union by size vs. rank

Either works; the goal is to keep trees shallow.

Boyer-Moore / Rabin-Karp

Boyer-Moore skips using a bad-character rule; Rabin-Karp uses rolling hashes to compare substrings in O(1) expected.

Common Mistakes

• Forgetting path compression (poor performance).
• Unioning without finding roots first.
• Off-by-one in KMP prefix/pattern indices.
• Assuming 1 << 31 is safe for signed int (shift into sign bit is UB).

Undefined Behavior

• Shifting a signed integer in UB ways (1 << 31). VERIFIED
• Reading out of bounds in string matching. VERIFIED

Portability

• Plain C. Bit intrinsics (__builtin_*) are GCC/Clang extensions; write

portable fallbacks or use C23 <stdbit.h>.

Under the Hood

Union-find is cache-friendly when arrays are contiguous. KMP is linear but constant-factor heavy; naive matching is often faster for short patterns. Bit operations map to single CPU instructions.

Practical Usage

• Use union-find for connected components and Kruskal's MST.
• Use KMP/Rabin-Karp for substring search in large text.
• Use bit algorithms for sets, flags, and low-level optimization.

Exercises

1. Implement union-find with path compression and union by rank. 2. Use union-find to count connected components in a grid. 3. Implement naive and KMP string search. 4. Implement popcount, clz, and "is power of two" with bit tricks.

Deep Challenge

Implement Kruskal's minimum spanning tree using union-find, and explain its O(E log E) complexity. Then optimize the union-find with path compression and rank and measure the effect.

Related Concepts

• c.ds.10 — bitsets/bitmaps.
• c.alg.3 — graph algorithms.
• c.ds.9 — tries.

References

• CLRS; Sedgewick; bit-twiddling hacks.

Verification

• Union-find near-O(1) amortized. VERIFIED
• KMP O(n+m). VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Union-find
• [ ] Path compression
• [ ] KMP string search
• [ ] Bit algorithms

Mastery levels