Как определить, что один массив является частью другого?

Question

Например: У меня есть массив

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

кто знает быстрый способ найти индекс массива тега? мне нужно что-то, как следующее:

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

последовательность может быть более чем один раз в ИПВ.

Решение: How to find index of sublist in list?

Answer 1

int FindIndexOfSeq<T>(byte[] src, byte[] tag) 
{ 
    Int32 tagCount = tag.Count();    

    // If `tag` is not empty and `src` contains `tag` 
    if (tagCount > 0 && src.Intersect(tag).Count() == tagCount) 
    { 
     // Find index of first element in `tag` 
     Int32 tagStartIndex = Array.IndexOf(src, tag.First()); 

     // Get the matching slice of `tag` from `src` 
     var newSrc = src.Skip(tagStartIndex).Take(tag.Count()).ToList(); 

     // Zip them together using their difference 
     var sum = Enumerable.Zip(tag, newSrc, (i1, i2) => Convert.ToInt32(i2 - i1)).Sum(); 

     // If total of their differences is zero, both sequences match 
     if (sum == 0) 
     { 
      // return starting index of `tag` in `src` 
      return tagStartIndex; 
     } 
    } 

    // return `Not Found` 
    return -1; 
} 

Answer 2

Вот один из способов до получения индекса

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

К сожалению, это очень медленно.

Если вы просто хотите знать, если все предметы в tag можно найти в src (в любом порядке), то

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!"); 

Answer 3

лучшее, что вы можете получить это O (м), но я немного сложным реализация. Если вы удовлетворены решением, которое имеет O (m * n) в худшем случае, вы можете перейти к решению ниже. Если ваши последовательности упорядочены, и начальный элемент в массиве tag присутствует только один раз в src, это также приведет к 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; 
    } 
} 

Я предположил, последовательность должны быть в таком порядке, и я только скомпилирован в Firefox, так что не уверен, если это работает :). Кроме того, я сделал его общим, поэтому он обрабатывает любые типы массивов, а не только байты.

UPDATE: Обновленный код компилируется и работает ... или мой простой тест работал.

Answer 4

Эта задача равна поисковой подстроке в строке. Для этого вы можете использовать любой алгоритм KMP для повышения производительности: http://exclusiveminds.com/2009/12/09/kmp-string-searching-algorithm-in-c/

Answer 5

Решение найдено.

How to find index of sublist in list?