How to find index of sublist in list?

Question

I am looking for some efficient way (in .NET), how to find if there is a sequence of bytes in some list of bytes and if there is any, index where the first starts.

For example let's say I have:

var sequence = new List<byte> { 5, 10, 2 };
var listOne = new List<byte> { 1, 3, 10, 5, 10, 2, 8, 9 };
var listTwo = new List<byte> { 1, 3, 10, 5, 2, 10, 8, 9 };

and the result should be that my sequence is on index 3 in the listOne and on index -1 (ie. it is not there) in the listTwo.

Of course I can loop through the list int by int and from every index and search if following numbers matches my sequence, but is there some more efficient way (for example using extension methods)?

Answer 1

This is essentially the same problem as substring searching (indeed, a list where order is significant is a generalisation of "string").

Luckily computer science has considered this problem frequently for a long time, so you get to stand on the shoulders of giants.

Take a look at the literature. Some reasonable starting points are:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://en.wikipedia.org/wiki/Rabin-karp

Even just the pseudocode in the wikipedia articles is enough to port to C# quite easily. Look at the descriptions of performance in different cases and decide which cases are most likely to be encountered by your code. (I'm thinking the first from what you say about the search-key list being short).

Answer 2

I think the cleanest way is create a generic extension method like this:

public static int SubListIndex<T>(this IList<T> list, int start, IList<T> sublist)
{
    for (int listIndex = start; listIndex < list.Count - sublist.Count + 1; listIndex++)
    {
        int count = 0;
        while (count < sublist.Count && sublist[count].Equals(list[listIndex + count]))
            count++;
        if (count == sublist.Count)
            return listIndex;
    }
    return -1;
}

to call in this way:

var indexOne = listOne.SubListIndex(0, sequence);
var indexTwo = listTwo.SubListIndex(0, sequence);

P.S. you can also start from a given index, if you need to search for more sublists occurrences