So I Wrote A Backward Version Of KMP Algorithm In C# That Searches String From Right


  • 0
    Y
            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 LastIndexOf(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;
            }
    

    Full source code can be seen here

    The method works like String.LastIndexOf() which searches string from the last character. The BuildTable() method is exactly same with normal KMP algorithm.

    I'm not sure if this is the best solution though.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.