using System.Collections.Generic;
private static Random Random { get; set; }
public static void Main()
Random = new Random(123);
new { Name = "a", Sequence = (IEnumerable<int>)new int[0], SubString = new[] { 1 } },
new { Name = "b", Sequence = (IEnumerable<int>)new[] { 0 }, SubString = new[] { 1 } },
new { Name = "c", Sequence = (IEnumerable<int>)new[] { 1 }, SubString = new[] { 1 } },
new { Name = "d", Sequence = (IEnumerable<int>)new[] { 1 }, SubString = new[] { 1 } },
new { Name = "e", Sequence = (IEnumerable<int>)new[] { 1, 1, 2, 2, 1, 2, 3, 1, 2, 4, 1, 2 }, SubString = new[] { 1, 2 } },
new { Name = "f", Sequence = (IEnumerable<int>)new[] { 1, 3, 2, 3, 4, 3 }, SubString = new[] { 1, 3, 2, 3 } },
new { Name = "g", Sequence = (IEnumerable<int>)new[] { 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 }, SubString = new[] { 1, 2, 1, 2 } },
new { Name = "h", Sequence = (IEnumerable<int>)new[] { 1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4 }, SubString = new[] { 1, 1, 2, 1, 2, 3, 1, 2, 3, 4 } },
new { Name = "i", Sequence = RandomDigits().Take(10000), SubString = new[] { 0, 1, 2, 3, 4 } }
Console.WriteLine(string.Join(", ", RandomDigits().Take(10)));
foreach(var row in testData)
var indices = string.Join(", ", row.Sequence.IndicesOf(row.SubString));
Console.WriteLine($"Name:{row.Name}, Indices:({indices})");
private static IEnumerable<int> RandomDigits()
yield return Random.Next(5);
public static bool Contains<T>(
this IEnumerable<T> source,
IEqualityComparer<T> equalityComparer = null)
throw new ArgumentNullException(nameof(pattern));
equalityComparer = equalityComparer ?? EqualityComparer<T>.Default;
return SearchImplementation(source, pattern, equalityComparer).Any();
public static IEnumerable<long> IndicesOf<T>(
this IEnumerable<T> source,
IEqualityComparer<T> equalityComparer = null)
throw new ArgumentNullException(nameof(pattern));
equalityComparer = equalityComparer ?? EqualityComparer<T>.Default;
return SearchImplementation(source, pattern, equalityComparer);
private static IEnumerable<long> SearchImplementation<T>(
IEnumerable<T> patternString,
IEqualityComparer<T> equalityComparer)
var tuple = GetSlide(patternString, equalityComparer);
var pattern = tuple.Pattern;
var patternLength = pattern.Count;
throw new ArgumentOutOfRangeException(
"The pattern must contain 1 or more elements.");
var buffer = new Dictionary<long, T>(patternLength);
using(var sourceEnumerator = source.GetEnumerator())
if (equalityComparer.Equals(pattern[patternIndex], t))
if (patternIndex == patternLength)
yield return sourceIndex - patternIndex;
patternIndex = slide[patternIndex - 1];
else if (more && !equalityComparer.Equals(pattern[patternIndex], t))
patternIndex = slide[patternIndex - 1];
sourceIndex = sourceIndex + 1;
private static bool FillBuffer<T>(
IDictionary<long, T> buffer,
if (!buffer.TryGetValue(sourceIndex, out value))
more = source.MoveNext();
buffer.Remove(sourceIndex - patternLength);
buffer.Add(sourceIndex, value);
private static SlideTuple<T> GetSlide<T>(
IEqualityComparer<T> equalityComparer)
var patternList = pattern.ToList();
var slide = new int[patternList.Count];
while (patternIndex < patternList.Count)
if (equalityComparer.Equals(
patternList[patternIndex],
slide[patternIndex] = length;
length = slide[length - 1];
slide[patternIndex] = length;
return SlideTuple<T>.Create(slide, patternList);
internal class SlideTuple<T>
IReadOnlyList<int> slide,
IReadOnlyList<T> pattern)
public IReadOnlyList<int> Slide { get; }
public IReadOnlyList<T> Pattern { get; }
internal static SlideTuple<T> Create(
IReadOnlyList<int> slide,
IReadOnlyList<T> pattern)
return new SlideTuple<T>(slide, pattern);