Поиск файла для последовательности байтов (C#)

Question

Я пишу приложение C#, в котором мне нужно искать файл (может быть очень большой) для последовательности байтов, и я не могу использовать какие-либо библиотеки для Сделай так. Итак, мне нужна функция, которая принимает байтовый массив в качестве аргумента и возвращает позицию байта, следующего за данной последовательностью. Функция не должна быть быстрой, она просто должна работать. Любая помощь будет принята с благодарностью :)

Answer 1

Если он не должен быть быстрым, вы можете использовать это:

int GetPositionAfterMatch(byte[] data, byte[]pattern) 
{ 
    for (int i = 0; i < data.Length - pattern.Length; i++) 
    { 
    bool match = true; 
    for (int k = 0; k < pattern.Length; k++) 
    { 
     if (data[i + k] != pattern[k]) 
     { 
     match = false; 
     break; 
     } 
    } 
    if (match) 
    { 
     return i + pattern.Length; 
    } 
    } 
} 

Но я действительно рекомендовал бы вам использовать алгоритм Кнута-Морриса-Пратта, это алгоритм, который в основном используется в качестве основы методов IndexOf для строк. Вышеупомянутый алгоритм будет работать очень медленно, за исключением небольших массивов и небольших шаблонов.

Answer 2

Прямолинейный подход, о котором говорил Туррау, работает, и для ваших целей, вероятно, достаточно хорош, так как вы говорите, что он не должен быть быстрым, тем более что для большинства практических целей алгоритм намного быстрее, чем наихудший случай O (n * m). (В зависимости от вашего шаблона, я думаю).

Для оптимального решения вы также можете проверить Knuth-Morris-Pratt algorithm, в котором используются частичные совпадения, в конце концов это O (n + m).

Answer 3

Вот выдержка из какого-то кода, который я использовал для поиска типа мальчика-моря. Это означает работать с файлами pcap, поэтому он управляет записью по записи, но должен быть достаточно простым для изменения, чтобы просто искать длинный двоичный файл. Это своего рода извлечение из некоторого тестового кода, поэтому я надеюсь, что у меня есть все, чтобы вы могли следовать. Также посмотрите на поиски мальчика-мура в википедии, так как это то, на чем оно основано.

int[] badMatch = new int[256]; 
byte[] pattern; //the pattern we are searching for 

//badMath is an array of every possible byte value (defined as static later). 
//we use this as a jump table to know how many characters we can skip comparison on 
//so first, we prefill every possibility with the length of our search string 
for (int i = 0; i < badMatch.Length; i++) 
{ 
    badMatch[i] = pattern.Length; 
} 

//Now we need to calculate the individual maximum jump length for each byte that appears in my search string 
for (int i = 0; i < pattern.Length - 1; i++) 
{ 
    badMatch[pattern[i] & 0xff] = pattern.Length - i - 1; 
} 

// Place the bytes you want to run the search against in the payload variable 
byte[] payload = <bytes> 

// search the packet starting at offset, and try to match the last character 
// if we loop, we increment by whatever our jump value is 
for (i = offset + pattern.Length - 1; i < end && cont; i += badMatch[payload[i] & 0xff]) 
{ 
    // if our payload character equals our search string character, continue matching counting backwards 
    for (j = pattern.Length - 1, k = i; (j >= 0) && (payload[k] == pattern[j]) && cont; j--) 
    { 
    k--; 
    } 
// if we matched every character, then we have a match, add it to the packet list, and exit the search (cont = false) 
    if (j == -1) 
    { 
    //we MATCHED!!! 
    //i = end; 
    cont = false; 
    } 
}