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.

• Installation
• Usage
• Examples
• Benchmarks

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.

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}.");

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

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