C# get part of array by array mask

Question

please help me. I would like get a part of array by mask array. This is my code:

byte[] source = new byte[] {97, 98, 99, 5, 15, 66, 77, 102, 0, 102, 0, 102, 0, 102, 0, 102, 0};
byte[] mask = new byte[] { 102, 0, 102, 0, 102, 0, 102, 0 };
byte[] result = EscapeArray(0, source, mask); 
private byte[] EscapeArray(int startIndex, byte[] source, byte[]mask)
{
   ???
}

Output from EscapeArray method will be 97, 98, 99, 5,15, 66, 77. Source array has any values but somewhere is mask sequence. EscapeArray returns part of array from startIndex to start of mask. I need very fast algorithm because this method will be carried out very often. Thanks

You should ask a question and provide what you've tried so far. — C4d, Nov 28 '16 at 12:56
I am sorry. This question is: **What will be the implementation methods EscapeArray?** — bluray, Nov 28 '16 at 12:58
There is not enough information here about the data to provide a "very fast" algorithm. At best a naive brute-force algorithm with *some* optimizations can be made. For instance, if either mask or source is static for a huge number of queries, a data structure more fitting than simple brute-force may be applied but there is no information about this here. — Lasse V. Karlsen, Nov 28 '16 at 13:01
judging by your example, and how I'm interpreting your question, why wouldn't the output be: "97, 98, 99, 5,15, 66, 77, 102, 0". If you're looking at the mask as "must be exactly this, in this order" then your source does contain that mask, but it has an additional "102, 0" in it, why would that be removed as well? oh "startIndex to start of mask"... disregard — Kritner, Nov 28 '16 at 13:05
arrays aren't a data structure suited for addition/deletetion — Sehnsucht, Nov 28 '16 at 13:07

score 1 · Answer 1 · edited May 23 '17 at 12:08

There we go. This is build according your comments that were deleted.

public static void Main()
{       
    int[] arr = new int[] { 1, 2, 3, 4, 5, 0, 0, 0, 0, 7, 8, 9};
    int[] mask = new int[] { 0, 0, 0, 0 };

    // Usage
    var subArr = SubArrayTillMask(2, arr, mask);

    Console.WriteLine(String.Join(",",subArr));
}


static int[] SubArrayTillMask(int start, int[] array, int[] mask ) 
{
    var foundPos = -1;

    var len = mask.Length;
    var limit = array.Length - len;
    for( var i = 0;  i <= limit;  i++ ) 
    {
        var k = 0;
        for( ;  k < len;  k++ ) {
            if( mask[k] != array[i+k] ) break;
        }
        if( k == len ) foundPos = i;
    }
    if(foundPos == -1)
        return array;

    return array.Skip(start).Take(foundPos-start).ToArray();
}

Example: .Net Fiddle
Peformance test: .Net Fiddle

Result: Tested 10000 lines in 0.018965 seconds.

Credits: Find an array (byte[]) inside another array?

Dmitry Bychenko · Accepted Answer · 2016-11-28T13:29:40.790

I suggest finding the index of the first mask ocurrence:

private static int MaskIndex(byte[] source, byte[] mask) {
  if (mask.Length == 0)
    return 0; // or source.Length; or throw exception

  for (int i = 0; i < source.Length - mask.Length + 1; ++i) {
    bool found = true;

    for (int j = 0; j < mask.Length; ++j)
      if (source[i + j] != mask[j]) {
        found = false;

        break;
      }

    if (found)
      return i;
  }

  return source.Length;
}

Having this you can implement EscapeArray as

private byte[] EscapeArray(int startIndex, byte[] source, byte[] mask) {
  int n = MaskIndex(source, mask);

  if (startIndex > n)
    return new byte[0]; // or throw exception 

  return source.Skip(startIndex).Take(n - startIndex).ToArray();
}

Test:

byte[] source = new byte[] 
  { 97, 98, 99, 5, 15, 66, 77, 102, 0, 102, 0, 102, 0, 102, 0, 102, 0 };
byte[] mask = new byte[] 
  { 102, 0, 102, 0, 102, 0, 102, 0 };

// 97, 98, 99, 5, 15, 66, 77  
Console.WriteLine(string.Join(", ", EscapeArray(0, source, mask)));

// 97, 98, 99, 5, 15, 66, 77, 102, 0, 102, 0, 102, 0, 102, 0, 102, 0
Console.WriteLine(string.Join(", ", EscapeArray(0, source, new byte[] {123})));

C# get part of array by array mask

2 Answers2