Есть ли быстрый алгоритм поиска подстроки с пропусками в строке?

Question

[12rbah]

Возможно некорректно задал вопрос, суть такая, что есть сигнатура 0xFF 0xDD ?? ?? 0xFF, где знаки вопроса там могут быть любые символы, ищется сигнатура в большом файле и если три этих символа встречаются в любой подстроке из 5 символов, единственное что пришло в голову, находить сигнатуру 0xFF 0xDD сохранять 5 байт(строку) в массив и потом еще раз отдельно пробегаться по этому массиву и проверять на наличие этих символов.
Просто подумал мб есть стандартный алгоритм для этого.

Comments

[Lynn «Кофеман»]

Есть стандартный механизм. Называется «регулярные выражения».

Впрочем в этом конкретном случае непонятно зачем нужно что-то сохранять в отдельный массив. Нужно просто найти 0xFF 0xDD сдвинуться на три байта вправо и проверить, что там 0xFF

[Lynn «Кофеман»]

Или даже вообще примерно так:

for(int i = 0; i < data.size - 4; i++) {
  if (data[i] == 0xFF && data[i+1] == 0xDD && data[i+4] == 0xFF) {
    // нашёл
  }
}

[12rbah]

Lynn «Кофеман», просто регулярные не очень быстрые поэтому их не хотел использовать, думаю буду использовать ваш вариант, согласен массив здесь лишний, тк сразу можно проверить сигнатуру, если хотите можете вынести в ответ ваш комментарий я отмечу его как решение.

[Lynn «Кофеман»]

> регулярные не очень быстрые
Это не совсем верно. Нужно смотреть на конкретные реализации. Вот, например https://github.com/yandex/pire

Но в общем-то для этой задачи это действительно оверкил.

Answer 1

[Lynn «Кофеман»]

Есть стандартный механизм. Называется «регулярные выражения».

Впрочем в этом конкретном случае непонятно зачем нужно что-то сохранять в отдельный массив. Нужно просто найти 0xFF 0xDD сдвинуться на три байта вправо и проверить, что там 0xFF. Примерно так (псевдокод):

for(int i = 0; i < data.size - 4; i++) {
  if (data[i] == 0xFF && data[i+1] == 0xDD && data[i+4] == 0xFF) {
    // нашёл
  }
}