Introduction

Searching for a very small substring inside a huge body of text is a classic performance problem. The best answer depends on whether you search once, search repeatedly, or stream the haystack from disk or the network. In many practical cases, the fastest solution is still the runtime’s built-in substring search, because standard libraries are heavily optimized in native code.

Start with the Built-In Search

For one small needle and one large haystack, the built-in search function is the correct baseline.

1haystack = "A" * 1_000_000 + "needle"
2needle = "needle"
3
4index = haystack.find(needle)
5print(index)

This is short, easy to read, and often faster than handwritten textbook algorithms. Measure this first before implementing anything more complicated.

Why the Naive Algorithm Wastes Work

The naive approach checks every possible starting position and compares the pattern character by character.

1def naive_find(text: str, pattern: str) -> int:
2    n = len(text)
3    m = len(pattern)
4
5    for i in range(n - m + 1):
6        if text[i:i + m] == pattern:
7            return i
8    return -1
9
10print(naive_find("abracadabra", "cada"))

This is easy to write, but it rechecks many characters after mismatches. On very large haystacks, that repeated work can dominate runtime.

Boyer-Moore-Horspool Fits the Small-Needle Case Well

When the needle is short, Boyer-Moore-style algorithms often work well because they compare from the end of the pattern and skip ahead aggressively.

1def bmh_search(text: str, pattern: str) -> int:
2    m = len(pattern)
3    n = len(text)
4    if m == 0:
5        return 0
6
7    skip = {pattern[i]: m - i - 1 for i in range(m - 1)}
8    i = 0
9
10    while i <= n - m:
11        j = m - 1
12        while j >= 0 and text[i + j] == pattern[j]:
13            j -= 1
14        if j < 0:
15            return i
16        i += skip.get(text[i + m - 1], m)
17
18    return -1
19
20print(bmh_search("A" * 1000 + "needle", "needle"))

This is attractive because preprocessing the small pattern is cheap and the skips can be large relative to the pattern length.

KMP Is Useful for Guaranteed Linear Time

Knuth-Morris-Pratt preprocesses the pattern so that the haystack is never revisited unnecessarily. Its main advantage is predictable worst-case linear performance.

1def prefix_table(pattern: str) -> list[int]:
2    table = [0] * len(pattern)
3    j = 0
4    for i in range(1, len(pattern)):
5        while j > 0 and pattern[i] != pattern[j]:
6            j = table[j - 1]
7        if pattern[i] == pattern[j]:
8            j += 1
9            table[i] = j
10    return table
11
12print(prefix_table("ababaca"))

KMP is a strong theoretical choice, especially when adversarial inputs matter, but it is often more code than needed for a single search task.

Rabin-Karp Helps in Hash-Oriented Workloads

Rabin-Karp uses rolling hashes and is more attractive when you are doing many related searches or comparing many candidate windows. For one tiny pattern, it is rarely the first choice, but it fits workloads where hashes are already part of the system.

The tradeoff is simple:

• efficient rolling comparison
• possible hash collisions
• extra verification needed after a hash match

If you use Rabin-Karp, always confirm a candidate hit with a real substring comparison.

Streaming Search for Massive Inputs

If the haystack is too large to load comfortably into memory, search in chunks and keep an overlap of len(needle) - 1 characters.

1def chunked_search(stream, needle: str, chunk_size: int = 1024) -> bool:
2    overlap = ""
3    while True:
4        chunk = stream.read(chunk_size)
5        if not chunk:
6            return False
7        text = overlap + chunk
8        if needle in text:
9            return True
10        overlap = text[-(len(needle) - 1):] if len(needle) > 1 else ""

That overlap is critical. Without it, a match split across two chunks will be missed.

Choose Based on the Workload

A practical rule of thumb:

• one search in one large string: built-in search first
• custom high-performance search with a short needle: Boyer-Moore-Horspool
• worst-case linear guarantee: KMP
• many rolling or related searches: Rabin-Karp
• huge streamed input: chunked search with overlap

Algorithm choice should follow the workload, not just textbook popularity.

Common Pitfalls

The biggest mistake is writing a custom algorithm before benchmarking the built-in search. Standard library implementations are often already heavily optimized.

Another issue is ignoring memory limits. If the haystack is massive, a perfect in-memory algorithm is still the wrong solution.

Developers also frequently forget chunk overlap in streaming search, which causes false negatives at chunk boundaries.

Summary

• Use the built-in substring search as the baseline for one-off searches.
• Boyer-Moore-Horspool is often a strong fit for a tiny needle in a huge haystack.
• KMP is valuable when worst-case guarantees matter.
• Rabin-Karp is useful when rolling hashes or repeated related searches are important.
• For enormous haystacks, streaming strategy can matter more than algorithm choice alone.