eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
обновлён 2 декабря!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме: rmn, parfetka (+1 невидимый пользователь)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Основной форум —› Нужен алгоритм
Посл.ответ Сообщение

Ранг: 323.6 (мудрец)
Статус: Участник
ILSpector Team

Создано: 4 июля 2008 09:22 New!
Цитата · Личное сообщение · #1

Собственно суть: нахождение строки содержащей к примеру "2f 25 ff 90 5a 34 ?? ?? 40 4a 5b ?? ??" в бинарном массиве данных. Посоветуйте лучший по вашему алгоритм поиска желательно название по автору и исходник пох на каком языке.


Ранг: 222.3 (наставник)
Статус: Участник

Создано: 4 июля 2008 09:37 New!
Цитата · Личное сообщение · #2

Вот мой алго на си. Требует доработки и оптимизации, но работает При желании его можно скомпилить в базонезависимый вариант и выложить в соседнем топике

{ Атач доступен только для участников форума } - BinarySearch.txt

Ранг: 323.6 (мудрец)
Статус: Участник
ILSpector Team

Создано: 4 июля 2008 09:58 New!
Цитата · Личное сообщение · #3

HandMill пишет:
Вот мой алго на си.
Уважаемый HandMill я Вас безмерно уважаю но все таки про алгоритм поиска по HandMill я весь инет перерыл но не нашел инфы. Еще раз спасибо но нужно что то покруче чем просто перебор я конечно же имею в виду скорость и устойчивость от размера искомой строки и основного массива.


Ранг: 748.2 (! !)
Статус: Участник
bytecode!

Создано: 4 июля 2008 10:01 · Поправил: 4kusNick New!
Цитата · Личное сообщение · #4

Medsft
http://diablo2oo2.di.funpic.de/downloads/dup.search.and.replace.patche ngine.sourcecode.rar http://diablo2oo2.di.funpic.de/downloads/dup.search.and.replace.patchengine.sourcecode.rar

Глянь, может, чем поможет.

Ранг: 323.6 (мудрец)
Статус: Участник
ILSpector Team

Создано: 4 июля 2008 10:05 · Поправил: Medsft New!
Цитата · Личное сообщение · #5

Есть вариант типа Алгоритм Кнута - Морриса - Пратта и Алгоритм Рабина - Карпа но я не знаю как туда вкурить неизвестную маску да и вообще он по моему с маской работать не будет а делить перед каждым проходом искомую строку это не правильно

Ранг: 16.8 (новичок)
Статус: Участник

Создано: 4 июля 2008 11:21 New!
Цитата · Личное сообщение · #6

Т.Кормен, Ч.Лейзерсон, Р.Ивест
АЛГОРИТМЫ пострение и анализ
МНЦМО, Москва, 2000
И будет счастье

Ранг: 323.6 (мудрец)
Статус: Участник
ILSpector Team

Создано: 4 июля 2008 11:42 · Поправил: Medsft New!
Цитата · Личное сообщение · #7

А можно не покупать книжку? Для счастья. У меня есть некоторое количество ссылок на поиск строк хотелось бы получить рекомендации по конкретным видам алго используемых на практике участниками форума.


Ранг: 126.7 (ветеран)
Статус: Участник
#CCh

Создано: 4 июля 2008 11:56 New!
Цитата · Личное сообщение · #8

Medsft пишет:
конкретным видам алго используемых на практике участниками форума

ну не знаю, как кто - я просто проверяю по DWORD'у и если он совпадает, то проверяю весь кусок памяти.. прекрасно компилируется VS в код с использованием REP STOS. Реализация нужна или это не достойно?


Ранг: 334.1 (мудрец)
Статус: Участник
born to be evil

Создано: 4 июля 2008 11:58 New!
Цитата · Личное сообщение · #9

Творил годика два назад типа этого. Юзается "?" вместо 1 символа, а не "??". MemC - так, не оптимизированый прототипчик, мона юзать pbyte() и т.п.

Function MemC(Var Buffer; xpos : LongWord) : Char;
Var Xchar : Char;
Begin
asm
push edi
lea edi,Buffer
mov edi,dword ptr [edi]
add edi,xpos
mov al,byte ptr [edi]
mov Xchar,al
pop edi
end;
MemC:=Xchar;
End;

Function FindMaskedCode(seq : String; buf : Pointer; bsize,firstpos : LongWord) : LongWord;
Var
found : Boolean;
i1 : LongWord;
i2,lsize : Word;
Begin
lsize:=length(seq);
i2:=0;
found:=false;
for i1:=firstpos to bsize-1do
begin
if(MemC(buf^,i1)=seq[1])or(seq[1]='?')then
for i2:=2to lsize do
if(seq[i2]<>'?')and(MemC(buf^,i1+i2-1)<>seq[i2])then break;
if i2>lsize then begin found:=true; break end;
end;
if not found then i1:=0;
FindMaskedCode:=i1;
End;

Ранг: 323.6 (мудрец)
Статус: Участник
ILSpector Team

Создано: 4 июля 2008 12:07 New!
Цитата · Личное сообщение · #10

Уже кое что а если добавить в маску кроме ?, звездочку * которая означает n-мерный массив неизвестных байт.


Ранг: 658.6 (! !)
Статус: Участник
CyberMonk

Создано: 4 июля 2008 13:16 New!
Цитата · Личное сообщение · #11

Medsft =) да мне тоже интересно .. когда топик еще паралельный тогда я свой закройю и продолжению сюда отправлю !

Ранг: 617.3 (!)
Статус: Участник

Создано: 4 июля 2008 14:02 New!
Цитата · Личное сообщение · #12

Надо было этот закрывать, там хоть название топика понятное.


Ранг: 520.5 (!)
Статус: Участник
Победитель турнира 2010

Создано: 4 июля 2008 16:16 New!
Цитата · Личное сообщение · #13

Вкусно разобрана тема регулярных выражений с классами на С++ (Лаборатория ЧПУ "СТАНКИН")

--> Link 1<-- http://www.ncsystems.ru/ru/programming/libs/regexp_filter/
--> Link 2<-- http://www.ncsystems.ru/ru/programming/libs/search_regexp/
--> Link 3<-- http://www.ncsystems.ru/ru/programming/libs/regexp_utility/


Ранг: 658.6 (! !)
Статус: Участник
CyberMonk

Создано: 4 июля 2008 16:37 New!
Цитата · Личное сообщение · #14

OKOB Ничего так сайт , подобных сайтов очень много =) уже видел на си на делфе , на си шарп на бэйсике даже =) , а на МАСМ нету , вообще тема легкая , просто так лениво все это разбирать , как рутинная работа. Или хотябы либ статическую на си делали с определением функций.

Кто знает достойные продукты арены REGEXP ? или их просто нет =) мне тут советовали как то на си шарп. Выглядела супер по возможностям а на деле отстой, половино не работает коректно )))) а потом тот кто советовал сам выкинул этот код. Вручную парсинг сделал и все.

Vovan666
ай неважно , там ссылка сюда всеравно идет , по поиску найдут кому надо.


Ранг: 387.4 (мудрец)
Статус: Участник
системщик

Создано: 4 июля 2008 23:21 New!
Цитата · Личное сообщение · #15

mak, regex работает с ascii текстом а не байтами. Минимальная версия - regex.c из вроде из glibc компилится на VC++ после мелких фиксов. Ессно google найдёт тебе много производных.

Ну а про оригинальный вопрос - частный случай когда только один pattern (шаблон) можно реализовать поиском первого байта и последующей проверкой всей последовательности. Это, думаю, самый простой и быстрый вариант. На много быстрее regex, кста. Ну а обобщённая версия задачи, с несколькими шаблонами и модификаторами типа ?+* - тут совсем другой разговор. Тут будет либо быстро и простые шаблоны, либо медленно с гибким интерпретатором сложного выражения - а ля полный posix regex.

Ранг: 52.1 (постоянный)
Статус: Участник

Создано: 5 июля 2008 13:32 · Поправил: Wyfinger New!
Цитата · Личное сообщение · #16

По-поводу поиска с маской *, можно разбить маску на куски известной длинны, а затем воспользоваться методом поиска Ахо-Корасика (поиск нескольких подстрок одновременно), затем, если искомые подстроки были найденны, проверить соответствует ли их порядок маске.


Ранг: 334.1 (мудрец)
Статус: Участник
born to be evil

Создано: 5 июля 2008 17:02 New!
Цитата · Личное сообщение · #17

Medsft
Для звездочки скомбинируй что-нить из этого: algolist.manual.ru/search/esearch/index.php
 eXeL@B —› Основной форум —› Нужен алгоритм

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS