The Backward Version of Knuth–Morris–Pratt Algorithm

Extensions.cs

using System;
using System.Collections.Generic;

namespace AlgorithmForce.Searching
{
    /* 
     * Full implementation:
     * https://github.com/rvhuang/kmp-algorithm/blob/master/src/AlgorithmForce.Searching/Extensions.cs
     */
    public static class Extensions
    {
        #region
        
        public static int LastIndexOf<T>(this IReadOnlyList<T> s, IReadOnlyList<T> t, int startIndex, IEqualityComparer<T> comparer)
            where T : IEquatable<T>
        {
            Validate(s, t, startIndex);

            // Follow the behavior of string.LastIndexOf(string) method. 
            if (t.Count == 0) return 0;
            if (s.Count == 0 || s.Count < t.Count) return -1;

            if (comparer == null) comparer = EqualityComparer<T>.Default;
            if (t.Count == 1) return LastIndexOfSingle(s, t[0], startIndex, comparer);

            var table = BuildTable(t, comparer);
            var i = 0;

            while (startIndex - i >= 0)
            {
                if (comparer.Equals(t[t.Count - i - 1], s[startIndex - i]))
                {
                    if (i == t.Count - 1)
                        return startIndex - t.Count + 1;
                    i++;
                }
                else
                {
                    if (table[i] > -1)
                    {
                        startIndex -= i;
                        i = table[i];
                    }
                    else
                    {
                        startIndex--;
                        i = 0;
                    }
                }
            }
            return -1;
        }
        
        internal static void Validate<T>(IReadOnlyList<T> s, IReadOnlyList<T> t, int startIndex)
        {
            if (s == null) throw new ArgumentNullException(nameof(s));
            if (t == null) throw new ArgumentNullException(nameof(t));

            if (startIndex < 0)
                throw new ArgumentOutOfRangeException(nameof(s), "Value is less than zero.");

            if (startIndex >= s.Count)
                throw new ArgumentOutOfRangeException(nameof(s), "Value is greater than the length of s.");
        }
        
        internal static int LastIndexOfSingle<T>(IReadOnlyList<T> s, T t, int startIndex, IEqualityComparer<T> comparer)
            where T : IEquatable<T>
        {
            var i = default(int);

            for (i = startIndex; i >= 0; i--)
            {
                if (comparer.Equals(s[i], t))
                    return i;
            }
            return -1;
        }

        internal static int[] BuildTable<T>(IReadOnlyList<T> t, IEqualityComparer<T> comparer)
            where T : IEquatable<T>
        {
            var table = new int[t.Count];
            var i = 2;
            var j = 0;

            table[0] = -1;
            table[1] = 0;

            while (i < t.Count)
            {
                if (comparer.Equals(t[i - 1], t[j]))
                {
                    table[i] = j + 1;
                    i++;
                    j++;
                }
                else if (j > 0)
                {
                    j = table[j];
                }
                else
                {
                    table[i] = 0;
                    i++;
                }
            }
            return table;
        }

        #endregion
    }
}