kmp-algorithm

The Most Complete .NET/C# Implementation of Knuth–Morris–Pratt Algorithm

View the Project on GitHub

Overview

KMP Algorithm .NET is the .NET implementation of Knuth–Morris–Pratt algorithm. The project defines a set of extension methods that apply the algorithm to strings and lists.

Unlike traditional KMP algorithm uses which are focused on string searching, the project provides a generic programming model of using KMP algorithm on IList(T) and IReadOnlyList(T), as long as type T is equatable. This expands the applicability of the algorithm, making searching an array of bytes in a longer array, or a collection of floats in an array of floats with same algorithm possible. In some cases, you may specify optional parameter IEqualityComparer(T) instance to provide different comparison behavior for type T.

The project also includes a “backward” version of KMP algorithm that searches the last occurrence of the target within the instance.

Getting Started

Using the extension method is similar to String.IndexOf, as following example shows.

    var s = Enumerable.Range(0, 100).ToList();
    var t = new[] { 5, 6, 7, 8, 9 };

    Console.WriteLine(s.IndexOf(t)); // 5

Because List(T) and array implements IReadOnlyList(T) interface, and Int32 is equatable, the extension method IndexOf is available for search.

Starting at a specified position is also supported. The following example searches an array of integer in collection, starting at index 6.

    var s = Enumerable.Range(0, 100).ToList();
    var t = new[] { 10, 11, 12, 13, 14 };

    Console.WriteLine(s.IndexOf(t, 6)); // 10

Similar to String.LastIndexOf, you can also search the last occurrence of target array in the collection. The backward version of KMP algorithm is used in the following example.

    var s = Enumerable.Range(0, 100).ToList();
    var t = new[] { 15, 16, 17, 18, 19 };

    Console.WriteLine(s.LastIndexOf(t)); // 15

Index Enumeration

The project provides iterator pattern for forward and backward index enumeration. The following example enumerates each of indexes by calling IndexesOf and LastIndexesOf method.

    var s = "1231abcdabcd123231abcdabcdabcdtrefabc";
    var t = new[] { 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'};

    foreach (var index in s.IndexesOf(t))
    {
        Console.WriteLine(index); // 4, 18, 22
    }

    foreach (var index in s.LastIndexesOf(t))
    {
        Console.WriteLine(index); // 22, 18, 4
    }

In this example, caller can start enumerating the collection of indexes before all indexes are found.

Platform

This project currently targets .NET Core only.