How to determine that one array is a part of another one?

Question

For instance: I have array

var src = new byte[] {1, 2, 3, 4, 5};
var tag = new byte[] {3, 4};

Who know fast method to find index of tag's array? I need something as following:

int FindIndexOfSeq(byte[] src, byte[] sequence);

a sequence can be in more than one times in src.

Solution: How to find index of sublist in list?

Answer 1

The best you can get is O(m), but that I slightly complex implementation. If you satisfy with a solution that has O(m*n) as worst case you can go with the solution below. If your sequences are ordered and the starting item in the tag array is only present one time in src this will also result in O(m).

class Program
{
    static void Main(string[] args)
    {
        var src = new byte[] { 1, 2, 3, 4, 5 };
        var tag = new byte[] { 3, 4 };
        var index = FindIndexOfSeq(src, tag);
        Console.WriteLine(index);
        Console.ReadLine();
    }
    static int FindIndexOfSeq<T>(T[] src, T[] seq)
    {
        int index = -1;
        for (int i = 0; i < src.Length - seq.Length + 1; i++)
        {
            bool foundSeq = true;
            for (int j = 0; j < seq.Length; j++)
            {
                foundSeq = foundSeq && src[i + j].Equals(seq[j]);
            }
            if (foundSeq)
            {
                index = i;
                break;
            }
        }
        return index;
    }
}

I assumed the sequence have to be in that order and I have only compiled it in firefox, so not sure if it works :). Also, I made it generic so it handles any type of arrays not just bytes.

UPDATE: The updated code compiles and work... or my simple test worked.

Answer 2

Here's one way to the get the index

for (int i = 0; i < (src.Length - tag.Length); i++ )
{
    if (tag.SequenceEqual(src.Skip(i).Take(tag.Length)))
        Console.WriteLine("It's at position " + i);
}

Unfortunately it's very slow.

If you just want to know if all of items in tag can be found in src (in any order) then

var src = new byte[] { 1, 2, 3, 4, 5 }; 
var tag = new byte[] { 4, 3 };

if (src.Intersect(tag).Count() == tag.Length)
    Console.WriteLine("tag can be found in src!");