Thirteen exact string-matching algorithms implemented in C, plus the harness that measures them against each other across text types, alphabet sizes and pattern lengths.
Built to answer a question textbooks usually leave open: which algorithm actually wins, and on what input. Worst-case complexity is not enough — for real texts the alphabet size and the pattern length decide the outcome.
| Family | Implementations |
|---|---|
| Prefix-based | kmp.h — Knuth–Morris–Pratt |
| Hashing | kr.h — Karp–Rabin · hash3.h |
| Suffix-based | bm.h — Boyer–Moore · skip.h · fs.h |
| Bit-parallel | sbndm.h · bndmq2.h · bsdm.h · bxs.h |
| Automaton | bom.h — Backward Oracle Matching |
| SIMD / word-level | ssef.h · ssm.h |
Each algorithm implements the interface in Algorithm.h, so adding one means dropping
in a header and registering it in Algorithms.h.
tests/ holds the inputs the measurements run against: natural-language text
(literature), source code (cfile), markup (html, json), a genome sequence
(genome), and random strings over alphabets of size 2, 32 and 64. Patterns come from
patternWordsDatasets; results land in tests/final_results.
cmake -B build && cmake --build build
./build/StringPatternAlgorithmsTestingpython_scripts/ post-processes the timings into comparison tables.
Course project, Taras Shevchenko National University of Kyiv.