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

25 Дек 2020 в 19:44
143 +1
0
Ответы
1

Для поиска подстроки с пропусками в строке существует алгоритм, называемый алгоритмом Вилдмана-Вана Wildman−WanalgorithmWildman-Wan algorithmWildmanWanalgorithm. Этот алгоритм позволяет искать подстроку, в которой некоторые символы могут пропускаться или заменяться любыми другими символами.

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

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

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

В целом, для решения вашей задачи можно комбинировать различные алгоритмы и подходы, в зависимости от специфики и требований задачи.

17 Апр 2024 в 21:25
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир