String Matching Algorithms

Implementation and experimental comparison of four classical string matching algorithms in C++:

• Naive String Matching
• Rabin-Karp
• Finite Automaton Matcher
• Knuth-Morris-Pratt (KMP)

The project implements the algorithms, validates their results against a common reference, and benchmarks their preprocessing and matching performance on several input scenarios.

Overview

String matching is the problem of finding all occurrences of a pattern P of length m inside a text T of length n. This project explores different algorithmic approaches to the problem and compares their practical behavior using the same benchmark framework.

The implementation is based on the string-matching algorithms presented in Chapter 32 of Introduction to Algorithms (CLRS).

Algorithms

Algorithm	Preprocessing	Matching	Main idea
Naive	O(1)	O((n-m+1)m) worst case	Tests the pattern at every possible shift
Rabin-Karp	O(m)	O(n+m) expected, O((n-m+1)m) worst case	Uses a rolling hash to filter candidate matches
Finite Automaton	preprocessing required	O(n)	Encodes pattern matching as state transitions
KMP	O(m)	O(n)	Uses prefix information to avoid rechecking characters

Features

• Independent implementations of all four algorithms
• Measurement of preprocessing and matching time
• Character-comparison counting for relevant algorithms
• Rabin-Karp hash-hit and spurious-hit statistics
• Multiple benchmark scenarios and input sizes
• Automatic export of results to CSV
• Correctness verification by comparing every algorithm with the Naive result
• Reproducible pseudo-random test generation using a fixed seed

Benchmark Scenarios

The program evaluates the algorithms on four types of input:

1. CLRS example - a small reference example used for correctness checking.
2. Random binary / random letters - randomly generated texts with small and larger alphabets.
3. Worst case for Naive - highly repetitive input designed to force many character comparisons.
4. Many matches - repetitive text in which the pattern occurs at almost every valid position.

Larger experiments use text sizes of 100,000, 500,000, and 1,000,000 characters.

Metrics

For each experiment, the program records:

• text length (n)
• pattern length (m)
• alphabet size
• number of matches
• number of benchmark repetitions
• preprocessing time
• matching time
• total time
• character comparisons
• Rabin-Karp hash hits
• Rabin-Karp spurious hits
• correctness status

Timing values are reported in milliseconds and averaged across repeated runs.

Project Structure

string-matching-algorithms/
├── src/
│   └── string_matching.cpp
├── results/
│   ├── results.csv
│   └── sample_output.txt
├── docs/
│   └── report.pdf
├── Makefile
├── .gitignore
└── README.md

Requirements

• C++ compiler with C++11 support
• Boost headers (boost::array)
• GNU Make

On Debian/Ubuntu, Boost can be installed with:

sudo apt install libboost-all-dev

Build

make

Equivalent command:

g++ -O2 -Wall -Wextra -std=c++11 src/string_matching.cpp -o string_matching

Run

./string_matching

or:

make run

To save the console output:

./string_matching | tee output.txt

The program automatically creates results.csv in the current directory.

Correctness Check

Every implementation is compared with the Naive algorithm's list of valid shifts. The correct column in results.csv should contain YES for every row.

A quick command-line check is:

grep ',NO$' results.csv

If the command produces no output, no mismatches were detected.

Example Results

The included benchmark data illustrates an important point: asymptotic complexity is not the only factor that determines practical runtime.

For example, on the provided worst-case input for the Naive algorithm with n = 1,000,000, the Naive implementation performs almost 50 million character comparisons, while KMP and the Finite Automaton avoid this repeated work. On random lowercase text, however, the Naive algorithm can still perform competitively because mismatches often occur after only a small number of comparisons.

The complete measurements are available in results/results.csv, with a formatted console example in results/sample_output.txt.

Academic Context

This project was developed as a university assignment focused on the implementation and experimental evaluation of classical string matching algorithms.

Reference

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Chapter 32: String Matching.