Please review my generic implementation of the Knuth-Morris-Pratt algorithm. Its modified to search a source of indeterminate length in a memory efficient fashion.
namespace Code
{
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
/// <summary>
/// A generic implementation of the Knuth-Morris-Pratt algorithm that searches,
/// in a memory efficient way, over a given <see cref="IEnumerator"/>.
/// </summary>
public static class KMP
{
/// <summary>
/// Determines whether the Enumerator contains the specified pattern.
/// </summary>
/// <typeparam name="T">The type of an item.</typeparam>
/// <param name="source">
/// The source, the <see cref="IEnumerator"/> must yield
/// objects of <typeparamref name="T"/>.
/// </param>
/// <param name="pattern">The pattern.</param>
/// <param name="equalityComparer">The equality comparer.</param>
/// <returns>
/// <c>true</c> if the source contains the specified pattern;
/// otherwise, <c>false</c>.
/// </returns>
/// <exception cref="ArgumentNullException">pattern</exception>
public static bool Contains<T>(
this IEnumerator source,
IEnumerable<T> pattern,
IEqualityComparer<T> equalityComparer = null)
{
if (pattern == null)
{
throw new ArgumentNullException(nameof(pattern));
}
equalityComparer = equalityComparer ?? EqualityComparer<T>.Default;
return SearchImplementation(pattern, source, equalityComparer).Any();
}
/// <summary>
/// Identifies indices of a pattern string in source.
/// </summary>
/// <typeparam name="T">The type of an item.</typeparam>
/// <param name="patternString">The pattern string.</param>
/// <param name="source">
/// The source, the <see cref="IEnumerator"/> must yield
/// objects of <typeparamref name="T"/>.
/// </param>
/// <param name="equalityComparer">The equality comparer.</param>
/// <returns>
/// A sequence of indices where the pattern can be found
/// in the source.
/// </returns>
/// <exception cref="ArgumentOutOfRangeException">
/// patternSequence - The pattern must contain 1 or more elements.
/// </exception>
private static IEnumerable<long> SearchImplementation<T>(
IEnumerable<T> patternString,
IEnumerator source,
IEqualityComparer<T> equalityComparer)
{
// Pre-process the pattern
var preResult = GetSlide(patternString, equalityComparer);
var pattern = preResult.Pattern;
var slide = preResult.Slide;
var patternLength = pattern.Count;
if (pattern.Count == 0)
{
throw new ArgumentOutOfRangeException(
nameof(patternString),
"The pattern must contain 1 or more elements.");
}
var buffer = new Dictionary<long, T>(patternLength);
var more = true;
long i = 0; // index for source
int j = 0; // index for pattern
while (more)
{
more = FillBuffer(
buffer,
source,
i,
patternLength,
out T t);
if (equalityComparer.Equals(pattern[j], t))
{
j++;
i++;
}
more = FillBuffer(
buffer,
source,
i,
patternLength,
out t);
if (j == patternLength)
{
yield return i - j;
j = slide[j - 1];
}
else if (more && !equalityComparer.Equals(pattern[j], t))
{
if (j != 0)
{
j = slide[j - 1];
}
else
{
i = i + 1;
}
}
}
}
/// <summary>
/// Fills the buffer.
/// </summary>
/// <remarks>
/// The buffer is used so that it is not necessary to hold the
/// entire source in memory.
/// </remarks>
/// <typeparam name="T">The type of an item.</typeparam>
/// <param name="buffer">The buffer.</param>
/// <param name="s">The source enumerator.</param>
/// <param name="i">The current index.</param>
/// <param name="patternLength">Length of the pattern.</param>
/// <param name="value">The value retrieved from the source.</param>
/// <returns>
/// <c>true</c> if there is potentially more data to process;
/// otherwise <c>false</c>.
/// </returns>
private static bool FillBuffer<T>(
IDictionary<long, T> buffer,
IEnumerator s,
long i,
int patternLength,
out T value)
{
bool more = true;
if (!buffer.TryGetValue(i, out value))
{
more = s.MoveNext();
if (more)
{
value = (T)s.Current;
buffer.Remove(i - patternLength);
buffer.Add(i, value);
}
}
return more;
}
/// <summary>
/// Gets the offset array which acts as a slide rule for the KMP algorithm.
/// </summary>
/// <typeparam name="T">The type of an item.</typeparam>
/// <param name="pattern">The pattern.</param>
/// <param name="equalityComparer">The equality comparer.</param>
/// <returns>A tuple of the offsets and the enumerated pattern.</returns>
private static (IReadOnlyList<int> Slide, IReadOnlyList<T> Pattern) GetSlide<T>(
IEnumerable<T> pattern,
IEqualityComparer<T> equalityComparer)
{
var patternList = pattern.ToList();
var slide = new int[patternList.Count];
int length = 0;
int i = 1;
while (i < patternList.Count)
{
if (equalityComparer.Equals(patternList[i], patternList[length]))
{
length++;
slide[i] = length;
i++;
}
else
{
if (length != 0)
{
length = slide[length - 1];
}
else
{
slide[i] = length;
i++;
}
}
}
return (slide, patternList);
}
}
}
I've used the non-generic IEnumerator
for representing the source as it allows a wider breadth of enumerators to represent data, including the TextElementEnumerator
. This enables the generic implementation to be used trivially to search Unicode strings with different normalizations, e.g.
namespace Code
{
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
class Program
{
static void Main(string[] args)
{
var testData = new List<(string Source, string Pattern)>
{
(string.Empty, "x"),
("y", "x"),
("x", "x"),
("yx", "x"),
("xy", "x"),
("aababccba", "abc"),
("1x2x3x4", "x"),
("x1x2x3x4x", "x"),
("1aababcabcd2aababcabcd3aababcabcd4", "aababcabcd"),
("ssstring", "sstring")
};
foreach(var d in testData)
{
var contains = Ext.Contains(d.Source, d.Pattern);
Console.WriteLine(
$"Source:\"{d.Source}\", Pattern:\"{d.Pattern}\", Contains:{contains}");
}
Console.ReadKey();
}
}
public static class Ext
{
public static bool Contains(
this string source,
string value,
CultureInfo culture = null,
StringComparer comparer = null)
{
comparer = comparer ?? StringComparer.Ordinal;
var sourceEnumerator = StringInfo.GetTextElementEnumerator(source);
var sequenceEnumerator = StringInfo.GetTextElementEnumerator(value);
var pattern = new List<string>();
while (sequenceEnumerator.MoveNext())
{
pattern.Add((string)sequenceEnumerator.Current);
}
return sourceEnumerator.Contains(pattern, comparer);
}
}
}
This question was improved following the answer here.
KMP.Contains
(pattern != null
) before an answer comes in. \$\endgroup\$