Introduction

Good substring-search benchmarks do not consist of one random text and one random pattern. To learn anything useful, you need a suite of cases that exercise different failure modes: easy matches, repeated prefixes, large alphabets, small alphabets, absent patterns, overlapping matches, and realistic corpora.

Start with the Questions You Want to Answer

Different substring algorithms optimize different cases. A benchmark should help you answer questions such as:

• how does the algorithm scale with text length
• how sensitive is it to alphabet size
• how does it behave on repetitive text
• how much preprocessing cost does the pattern introduce
• how does it perform when there are many matches versus none

If the test set cannot separate those dimensions, the benchmark result is mostly noise.

Essential Test Categories

A good suite should include at least these categories.

1. No Match

The pattern never appears in the text.

text = "a" * 1000000
pattern = "b"

This measures scanning cost without match handling.

2. Single Match Near the End

text = "a" * 999999 + "needle"
pattern = "needle"

This stresses worst-case scan length in a simple way.

3. Many Matches

text = "abababababababab"
pattern = "ab"

This reveals how the implementation behaves when reporting many match positions.

4. Overlapping Matches

text = "aaaaaa"
pattern = "aaa"

Algorithms must decide whether and how to continue after a match. Overlapping hits are a classic correctness and performance case.

5. Long Repeated Prefixes

text = "a" * 1000000
pattern = "a" * 1000 + "b"

This is especially important for naïve search because it triggers lots of partial-prefix comparisons. It is a standard stress case for algorithms such as KMP, Boyer-Moore variants, and Z-based methods.

Vary the Alphabet Size

Alphabet size matters because it changes how often accidental partial matches occur.

Use at least:

• binary or tiny alphabet such as only a and b
• medium alphabet such as lowercase English text
• large alphabet such as random bytes or Unicode-heavy text

For example:

1import random
2import string
3
4def random_text(length, alphabet):
5    return "".join(random.choice(alphabet) for _ in range(length))
6
7small = random_text(100000, "ab")
8medium = random_text(100000, string.ascii_lowercase)
9large = random_text(100000, string.printable)

A tiny alphabet tends to create more repeated prefixes and therefore exposes poor mismatch behavior.

Use Realistic Corpora Too

Synthetic adversarial tests are essential, but real data still matters. Add workloads such as:

• source code files
• natural-language text
• DNA-style sequences
• log files

Each data type has its own structure. A benchmark based only on random input often misses the repetition patterns that matter in production.

Separate Preprocessing Time from Search Time

Algorithms such as Knuth-Morris-Pratt, Boyer-Moore, and suffix-based methods often preprocess the pattern. Benchmark that cost separately from the search pass.

1import time
2
3start = time.perf_counter()
4table = [0] * len(pattern)  # placeholder for preprocessing
5prep_time = time.perf_counter() - start
6
7start = time.perf_counter()
8# search(text, pattern, table)
9search_time = time.perf_counter() - start

If you merge both costs into one number, you may misjudge short-pattern versus long-pattern workloads.

Measure More Than Runtime

Useful metrics include:

• wall-clock time
• comparisons performed
• memory usage
• preprocessing time
• throughput in bytes or characters per second

Comparison counts are especially valuable because they are less sensitive to unrelated machine noise than raw timing alone.

Correctness Must Be Verified First

A fast incorrect algorithm is not a good algorithm. Every benchmark harness should cross-check the candidate implementation against a simple trusted reference.

1def naive_find_all(text, pattern):
2    result = []
3    for i in range(len(text) - len(pattern) + 1):
4        if text[i:i + len(pattern)] == pattern:
5            result.append(i)
6    return result

Run the optimized implementation and the reference implementation on the same test cases and compare match positions before timing large runs.

Common Pitfalls

• Benchmarking only random text, which hides the adversarial repeated-prefix cases that break weaker algorithms.
• Reporting one average runtime without separating preprocessing cost from the search pass.
• Ignoring correctness validation and trusting performance numbers from an implementation that may return wrong matches.
• Using only one alphabet size, even though substring-search behavior changes dramatically between tiny and large alphabets.
• Measuring only one match scenario instead of covering no-match, single-match, many-match, and overlapping-match cases.

Summary

• A strong substring benchmark suite mixes adversarial synthetic data with realistic corpora.
• Repetitive texts, overlapping matches, and absent patterns are mandatory cases.
• Alphabet size and pattern structure strongly influence algorithm behavior.
• Preprocessing time should be measured separately from search time when applicable.
• Always verify correctness against a simple reference implementation before trusting the benchmark results.