/Knuth-Morris-Pratt

Implementation of the Knuth-Morris-Pratt Algorithm

Primary LanguageC#MIT LicenseMIT

Knuth-Morris-Pratt Algorithm

This repository contains an implementation of the Knuth-Morris-Pratt algorithm in C#. The KMP algorithm is a string searching algorithm that efficiently finds occurrences of a pattern within a larger text.

Table of Contents

Installation

Requires .NET 8

To use this implementation of the KMP algorithm, follow these steps:

  1. Clone the repository: git clone https://github.com/your-username/Knuth-Morris-Pratt.git
  2. Restore the NuGet packages by running dotnet restore in the project directory.
  3. Build the project by running dotnet build in the project directory.
  4. Run the tests by running dotnet test in the project directory.

Usage

To use the KMP algorithm, use it like this:

using Knuth_Morris_Pratt;

var pattern = "ABCDABD";
var text = "ABC ABCDAB ABCDABCDABDE";

var occurrencesIndex = KnuthMorrisPrattAlgorithm.Search(pattern, text);
Console.WriteLine($"Pattern '{pattern}' occurs at index {occurrencesIndex}.");

Benchmarks

The benchmarks can be found in the .Benchmark project and compare the KMP with the naive string search and the boyer moore string search algorithms.

The text used for the benchmarks is "The Great Gatsby" by F. Scott Fitzgerald from the Project Gutenberg. The patterns used for the benchmarks is "facility", "thatched", and "Zelda" which represent words from the start, middle and end of the text.

Set the configuration to Release Mode before running the benchmarks

My Results


BenchmarkDotNet v0.13.12, macOS Sonoma 14.4.1 (23E224) [Darwin 23.4.0]
Apple M1 Pro, 1 CPU, 8 logical and 8 physical cores
.NET SDK 8.0.100
  [Host]     : .NET 8.0.0 (8.0.23.53103), Arm64 RyuJIT AdvSIMD
  DefaultJob : .NET 8.0.0 (8.0.23.53103), Arm64 RyuJIT AdvSIMD
Method Pattern Mean Error StdDev Median Ratio RatioSD Gen0 Gen1 Gen2 Allocated Alloc Ratio
OriginalIndexOf facility 29,284.5 ns 41.59 ns 38.90 ns 29,267.4 ns 1.00 0.00 - - - - NA
KnuthMorrisPrattSearch facility 262,096.8 ns 174.57 ns 163.29 ns 262,077.6 ns 8.95 0.01 - - - 56 B NA
NaiveSearch facility 256,677.1 ns 158.16 ns 147.95 ns 256,638.2 ns 8.76 0.01 - - - - NA
BoyerMooreSearch facility 213,310.1 ns 1,384.86 ns 1,295.40 ns 213,120.9 ns 7.28 0.04 232.6660 232.6660 66.6504 262403 B NA
OriginalIndexOf thatched 15,903.1 ns 10.20 ns 9.04 ns 15,905.0 ns 1.00 0.00 - - - - NA
KnuthMorrisPrattSearch thatched 169,320.8 ns 323.91 ns 270.48 ns 169,287.4 ns 10.65 0.02 - - - 56 B NA
NaiveSearch thatched 166,236.2 ns 680.59 ns 636.63 ns 166,226.0 ns 10.46 0.04 - - - - NA
BoyerMooreSearch thatched 135,909.5 ns 2,676.72 ns 4,167.34 ns 133,725.5 ns 8.73 0.28 233.3984 233.3984 66.4063 262389 B NA
OriginalIndexOf Zelda 133.6 ns 0.56 ns 0.52 ns 133.9 ns 1.00 0.00 - - - - NA
KnuthMorrisPrattSearch Zelda 990.3 ns 0.73 ns 0.68 ns 990.2 ns 7.41 0.03 0.0076 - - 48 B NA
NaiveSearch Zelda 983.9 ns 4.00 ns 3.34 ns 983.1 ns 7.36 0.04 - - - - NA
BoyerMooreSearch Zelda 77,068.6 ns 398.64 ns 372.89 ns 77,028.1 ns 576.76 3.85 233.2764 233.2764 66.6504 262368 B NA