How to search an array with array?

Question

I have 2 byte arrays:

    Dim A() As Byte = {1, 2, 3, 4, 5, 6, 7, 8, 9}
    Dim B() As Byte = {5, 6, 7}

Now I want to find the occurance of the full B in A. I tried Array.IndexOf(A, B) with no luck. Is there a simple way to search an array by array without the need to use any loops?

It should find the index (position) of 5,6,7 in the same order as in B(). If A() contains {1,2,3,4,7,6,5,9} it should return false or -1 because they are not in the same order.

Answer 1

The following Linq statement will give an IEnumerable<int> containing the positions of b in a (or an empty set if none occur):

Enumerable
    .Range( 0, 1 + a.Length - b.Length )
    .Where( i => a.Skip(i).Take(b.Length).SequenceEqual(b) );

I have no idea how to translate to VB.NET.

Answer 2

This might work, but it's C# and uses a loop:

private static int[] GetIndicesOf(byte[] needle, byte[] haystack)
{
    int[] foundIndices = new int[needle.Length];

    int found = 0;

    for (int i = 0; i < haystack.Length; i++)
    {

        if (needle[found] == haystack[i])
        {
            foundIndices[found++] = i;

            if (found == needle.Length)
                return foundIndices;
        }
        else
        {
            i -= found;   // Re-evaluate from the start of the found sentence + 1
            found = 0;    // Gap found, reset, maybe later in the haystack another occurrance of needle[0] is found
            continue;
        }
    }

    return null;            
}

Tested with input:

Byte[] haystack = { 5, 6, 7, 8, 9, 0, 5, 6, 7 };
Byte[] needle = { 5, 6, 7 };
// Returns {0, 1, 2}

Byte[] haystack = { 5, 6, 0, 8, 9, 0, 5, 6, 7 };
Byte[] needle = { 5, 6, 7 };
// Returns {6, 7, 8}

Byte[] haystack = { 5, 6, 0, 7, 9, 0, 5, 6, 8 };
Byte[] needle = { 5, 6, 7 };
// Returns null

Byte[] haystack = { 1, 2, 1, 2, 2 };
Byte[] needle = { 1, 2, 2 };
// Returns {2, 3, 4}

Byte[] haystack = { 1, 2, 1, 2, 1, 2, 3 };
Byte[] needle = { 1, 2, 1, 2, 3 };
// Returns {2, 3, 4, 5, 6}

Byte[] haystack = { 1, 1, 1, 1, 2 };
Byte[] needle = { 1, 2 };
// Returns {3, 4}

But the Linq implementation of @spender looks nicer. :-P

Answer 3

How about creating a method that:

1. Concatinates the elements of the searched list to one string
2. Concatinates the elements of the list to search for to one string
3. Looks in the first string for the precense of the second string

Like so:

public bool IsSubSetOf(IList<int> list1, IList<int> list2){
   var string1 = string.Join("", list1);
   var string2 = string.Join("", list2);
   return string1.Contains(string2);
}

Not tested...

Answer 4

An efficient way of solving this problem in general is the KMP algorithm. Quick googling suggest that a .NET implementation may be found here. It's implementational pseudocode is availible from Wikipedia.

An inefficient, but harmlessly easy to code way is presented in one of the links above as follows:

int[] T = new[]{1, 2, 3, 4, 5};
int[] P = new[]{3, 4};

for (int i = 0; i != T.Length; i++)
{
    int j = 0
    for (;i+j != T.Length && j != P.Length && T[i+j]==P[j]; j++);
    if (j == P.Length) return i;
}

Answer 5

My take would be:

public static int Search<T>(T[] space, T[] searched) {
  foreach (var e in Array.FindAll(space, e => e.Equals(searched[0]))) {
    var idx = Array.IndexOf(space, e);
    if (space.ArraySkip(idx).Take(searched.Length).SequenceEqual(searched))
      return idx;
  }
  return -1;
}

public static class Linqy {
  public static IEnumerable<T> ArraySkip<T>(this T[] array, int index) {
    for (int i = index;  i < array.Length; i++) {
      yield return array[i];
    }
  }
}

As always, it depends on your data whether this is "good enough" or you will have to resort to more complex yet efficient algorithms. I introduced an arrayskip as the Linq skip does indeed only assume the IEnumerable interface and would enumerate up to the index.