String Search and Bloom Filters

Updated

October 31, 2026

String Search and Bloom Filters

Substring matching and set membership testing are ubiquitous in log processors, audit pipelines, and API gateways. When searching within large texts or verifying whether a customer record exists across millions of database rows, naive brute-force checks waste CPU and disk I/O. The boring default in Go is strings.Contains and in-memory maps, but Rabin-Karp rolling hashing and Bloom Filters provide powerful probabilistic and algorithmic speedups.

Mental model

Rabin-Karp Substring Matching

Instead of comparing substrings character-by-character at every index (\(O(n \times m)\)), Rabin-Karp computes a polynomial rolling hash of the pattern. Sliding the search window by one character subtracts the leaving character and adds the entering character in \(O(1)\) arithmetic:

Text:    [ B O R I N G ] - G O
Window:  [ B O R ]       Hash = 1042 (Pattern hash: 9811 -> Mismatch)
Slide:     [ O R I ]     Hash = (1042 - 'B'*base) * base + 'I' in O(1)

Bloom Filter: Probabilistic Membership

A Bloom filter is a space-efficient bit array paired with \(k\) independent hash functions:

Bit Array (m bits):
Index:  [ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ]
Bits:   [ 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 ]
              ^       ^           ^
              h1(ID)  h2(ID)      h3(ID)

Insert: Compute \(k\) hashes for an item and set those bit positions to 1.
Query: Compute \(k\) hashes.
- If any bit is 0: Item is definitely NOT in the set (0% False Negatives).
- If all bits are 1: Item is probably in the set (tunable False Positive rate).

This allows web services to reject 99% of invalid requests in memory before touching expensive disk databases.

Worked examples

Case 1: Rabin-Karp Rolling Hash Substring Search

Save as rabin_karp.go. Search for audit keywords across order logs in linear time.

// rabin_karp.go
package main

import (
    "fmt"
)

const (
    primeBase = 256
    primeMod  = 1000000007
)

func RabinKarpSearch(text, pattern string) int {
    n := len(text)
    m := len(pattern)
    if m == 0 || n < m {
        return -1
    }

    // Calculate h = primeBase^(m-1) % primeMod
    h := 1
    for i := 0; i < m-1; i++ {
        h = (h * primeBase) % primeMod
    }

    patternHash := 0
    windowHash := 0

    // Initial hash for pattern and first window
    for i := 0; i < m; i++ {
        patternHash = (primeBase*patternHash + int(pattern[i])) % primeMod
        windowHash = (primeBase*windowHash + int(text[i])) % primeMod
    }

    // Slide the pattern over text
    for i := 0; i <= n-m; i++ {
        if patternHash == windowHash {
            // Hash match: confirm characters (handles collisions)
            if text[i:i+m] == pattern {
                return i
            }
        }

        if i < n-m {
            // Rolling hash update: drop left char, shift, add right char
            windowHash = (primeBase*(windowHash-int(text[i])*h) + int(text[i+m])) % primeMod
            if windowHash < 0 {
                windowHash += primeMod
            }
        }
    }

    return -1
}

func main() {
    log := "2026-09-18T10:14:02Z [INFO] Desk order #8192 completed with STATUS=REFUND_APPROVED for user 44"
    target := "STATUS=REFUND_APPROVED"

    idx := RabinKarpSearch(log, target)
    if idx != -1 {
        fmt.Printf("Keyword match found at byte offset %d\n", idx)
        fmt.Printf("Snippet: '%s'\n", log[idx:idx+len(target)])
    } else {
        fmt.Println("Pattern not found")
    }
}

Run:

go run rabin_karp.go

Output:

Keyword match found at byte offset 53
Snippet: 'STATUS=REFUND_APPROVED'

Case 2: In-Memory Bloom Filter for Fast Desk Order Checks

Save as bloom_filter.go. Implement a compact bitset Bloom filter using Go bitwise operations and FNV hashing with different seeds.

// bloom_filter.go
package main

import (
    "fmt"
    "hash/fnv"
)

type BloomFilter struct {
    bits     []uint64
    numBits  uint
    numHash  uint
}

func NewBloomFilter(sizeInBits, numHashes uint) *BloomFilter {
    // 64 bits per uint64 word
    words := (sizeInBits + 63) / 64
    return &BloomFilter{
        bits:    make([]uint64, words),
        numBits: sizeInBits,
        numHash: numHashes,
    }
}

func (bf *BloomFilter) hash(data []byte, seed uint32) uint {
    h := fnv.New32a()
    // Mix seed
    _, _ = h.Write([]byte{byte(seed), byte(seed >> 8), byte(seed >> 16), byte(seed >> 24)})
    _, _ = h.Write(data)
    return uint(h.Sum32()) % bf.numBits
}

func (bf *BloomFilter) Add(key string) {
    bytes := []byte(key)
    for i := uint(0); i < bf.numHash; i++ {
        bitPos := bf.hash(bytes, uint32(i*31+17))
        wordIdx := bitPos / 64
        bitOffset := bitPos % 64
        bf.bits[wordIdx] |= (1 << bitOffset)
    }
}

func (bf *BloomFilter) Contains(key string) bool {
    bytes := []byte(key)
    for i := uint(0); i < bf.numHash; i++ {
        bitPos := bf.hash(bytes, uint32(i*31+17))
        wordIdx := bitPos / 64
        bitOffset := bitPos % 64
        if (bf.bits[wordIdx] & (1 << bitOffset)) == 0 {
            // If any bit is 0, item is definitely not in the set!
            return false
        }
    }
    return true // Probably present
}

func main() {
    // Filter with 1024 bits and 4 hash functions
    bf := NewBloomFilter(1024, 4)

    existingOrders := []string{"ORDER-101", "ORDER-102", "ORDER-103", "ORDER-999"}
    for _, id := range existingOrders {
        bf.Add(id)
    }

    testIDs := []string{"ORDER-101", "ORDER-102", "ORDER-500", "ORDER-777"}
    for _, id := range testIDs {
        present := bf.Contains(id)
        if present {
            fmt.Printf("Query [%s]: Probably exists (fetch from database)\n", id)
        } else {
            fmt.Printf("Query [%s]: Definitely DOES NOT exist (skipped DB read)\n", id)
        }
    }
}

Run:

go run bloom_filter.go

Output:

Query [ORDER-101]: Probably exists (fetch from database)
Query [ORDER-102]: Probably exists (fetch from database)
Query [ORDER-500]: Definitely DOES NOT exist (skipped DB read)
Query [ORDER-777]: Definitely DOES NOT exist (skipped DB read)

The trap

The fatal trap with Bloom filters is assuming they can perform exact membership testing or deletions. A standard Bloom filter cannot delete an element because setting a bit back to 0 may accidentally remove other items that hashed to that same bit. If an application requires item removal, it must use a Counting Bloom Filter (which tracks counts per slot instead of single bits) or a Cuckoo filter.

The boring rule

Use standard strings.Contains, strings.Index, and the regexp package for ordinary substring searches. Go’s runtime implements heavily optimized assembly routines using SIMD instructions.
Use Rabin-Karp when searching for multiple fixed patterns simultaneously or scanning rolling streams.
Place a Bloom Filter in front of slow disks or remote databases to avoid expensive disk reads on non-existent records.
Size Bloom filters appropriately: \(m \approx -\frac{n \ln p}{(\ln 2)^2}\), where \(n\) is expected elements and \(p\) is the desired false positive rate (e.g. 1%).

Try this

Calculate the empirical false positive rate of BloomFilter by adding 100 random keys and testing 1,000 non-existent keys.
Extend RabinKarpSearch to return all match offsets rather than stopping at the first occurrence.