И еще один вопрос. Хочу написать поиск вхождения подстроки в тексте

Question

И еще один вопрос. Хочу написать поиск вхождения подстроки в тексте

большого размера. Пока придумал только вот-такой алгоритм:

Исходный шаблон проходим побайтно через mov ax, [ebx] . Очередной байт ищем через scansb. Если не находим откатываемся на байт назад и снова ищем следующее вхождение. И так до тех пор, пока не будет достигнут конец шаблона — вхождение найдено, либо конец текста — вхождения нет.

Но может быть есть еще какой вариант алгоритма?

#assembler #programming #russian

0

20.06.2022

13 ответов

34 просмотра

место имение рейверы

КМП вам в помощь , или Рабин-карп

0

20.06.2022

Alexander Morozov Автор вопроса

Сергей
А если UTF8 или 16? Не, там немного сложнее. Пару ...

Я ожидаю, что подстрока и строка в одной кодировке (пусть даже это utf-8) в бинарном виде также сохранят свойство вхождение одной в другую. Или уже с этим возможны проблемы?

0

20.06.2022

Alexander Morozov Автор вопроса

место имение рейверы
КМП вам в помощь , или Рабин-карп

А можно расшифровку для гугления?

0

20.06.2022

Сергей

Alexander Morozov
Я ожидаю, что подстрока и строка в одной кодировке...

нет-нет. Я тоже приводил всё к одному знаменателю, а потом уже сравнивал побайтово. Просто про этот нюанс отметил, не более чем как для информации

0

20.06.2022

$Aiwan \ (•◡•) / _bot-$ Aiwan \ (•◡•) / _bot

вариантов нет, но есть простор для оптимизации. в зависимости от длины шаблона первые итерации искать через sse/avx, а последние побайтно. за раз по 16/32/64 байт, или по 8/4/2 через scas

0

20.06.2022

Alexander Morozov Автор вопроса

Aiwan \ (•◡•) / _bot
вариантов нет, но есть простор для оптимизации. в ...

А при поиске через границы слова, двойного слова и т.п. проблемы не возникнет?

0

20.06.2022

$Aiwan \ (•◡•) / _bot-$ Aiwan \ (•◡•) / _bot

Alexander Morozov
А при поиске через границы слова, двойного слова и...

эт уже будет на конечном жтапе через scasb

0

20.06.2022