4
\$\begingroup\$

The generic version of extension method is aimed to work like String.LastIndexOf which can search t from the last position of s. The BuildTable method is exactly same with the method used by normal KMP algorithm, which is to determine the differences between each element.

I am not sure if this is the best solution as there is a question about reusing BuildTable method can provide best performance in this case.

Complete source code can be viewed here. Creating issues at GitHub is also welcome.


    public static int LastIndexOf<T>(this IReadOnlyList<T> s, IReadOnlyList<T> t, 
        int startIndex, IEqualityComparer<T> comparer) where T : IEquatable<T>
    {
        /*
         * Parameters check is omitted in this snippet.
         */

        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;
    }

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.