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
– C4d, Commented Nov 28, 2016 at 12:56
I am sorry. This question is: What will be the implementation methods EscapeArray? — bluray
– bluray, Commented Nov 28, 2016 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
– Lasse V. Karlsen, Commented Nov 28, 2016 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
– Kritner, Commented Nov 28, 2016 at 13:05
arrays aren't a data structure suited for addition/deletetion — Sehnsucht
– Sehnsucht, Commented Nov 28, 2016 at 13:07

Dmitrii Bychenko · Accepted Answer · 2016-11-28 13:29:40Z

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})));

Community · Accepted Answer · 2017-05-23 12:08:39Z

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?

Collectives™ on Stack Overflow

C# get part of array by array mask

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related