Добрый вечер. Какой самый оптимальный вариант по скорости/размеру Вы знаете? Написал свой вариант, но мне кажется что, он не самый оптимальный и есть во много раз лучше. Хотелось бы увидеть Ваши варианты. Примечание #1: Поиск по форуму, на момент создания темы не работал. Примечание #2: Собственный вариант представлю чуть позже.
Про поиск можно книгу, килограм в 10 написать. Всё от конкретных задач, образцов и текстов зависит. А образно говоря, оптимальный вариант, как раз постом ниже обсуждали... Правда напрямую про это не говорили
вот тут некоторые товарищи советовали буку дэн гасфилд "строки, деревья и последовательности в алгоритмах" всего 658 страничек
2010_07_14 Сильно ее не тестировал. В отличии от предыдущих моих попыток, должна работать нормально. |_через полгода скажу, что ни одного жука не увидел. Код (Text): Итак. Процедура ищет вхождение подстроки в строку. str = искомое lstr = длина искомого src = тут будем искать lsrc = длина рабочего потока start = старт с 1 относительно головы src(DF=0) или хвоста(DF=1) wall = стоп с 1 относительно головы src(DF=0) или хвоста(DF=1) работа продолжается по данную позицию eax <- результат, приведенный к DF=0 I've not tested it much. Still it does good unlike the one before. Код (Text): ; Searches for a byte pattern in another one. Count from 1. ; result <- eax. ; restore: eflags. ; Both search directions supported but result is always given as if eflags.df=0. ; -str = wanted. ; -lstr = length of str in bytes. ; -src = source. ; -lsrc = length of src in bytes. ; -start = job start relatively src's head(eflags.df=0) or tail(eflags.df=1). ; -stop = job end(wall) relatively src's head(eflags.df=0) or tail(eflags.df=1). dbgstr pos proc pos uses ebx ecx edx esi edi, str:dword, lstr:dword, src:dword, lsrc:dword, start:dword, stop:dword pushfd xor eax,eax ; result=0 cdq or edx,[lstr] jz .exit ; length(str)=0 mov ecx,eax or ecx,[lsrc] jz .exit ; length(src)=0 cmp edx,ecx ja .exit ; length(str)>length(src) mov ebx,eax or ebx,[start] jz .exit ; start=0 cmp ebx,ecx ja .exit ; start>length(src) mov esi,eax or esi,[stop] jz @f ; stop=0 cmp esi,ecx ja @f ; stop>length(src) -> stop=0 cmp esi,ebx jbe .exit ; start>=stop lea ecx,[esi-1] ; ecx>0 <- const @@: dec ebx sub ecx,ebx ; ecx>0 <- const dec edx ; cmpsb.ecx sub ecx,edx ; scasb.ecx jbe .exit ; over(src)flow bt dword[esp],10 mov esi,[str] mov edi,[src] lea eax,[edi+ebx] cmovnc edi,eax jnc @f ; search TO bigger address neg ebx add ebx,[lsrc] lea edi,[edi+ebx-1] add esi,edx ; search FROM bigger address @@: lodsb @@: repne scasb jne .fail ; no str[1] in src test edx,edx jz @f ; length(str)=1 -> no need to check the rest(edx) push esi edi mov ebx,ecx mov ecx,edx repe cmpsb pop edi esi je @f ; str rest(edx) match mov ecx,ebx jecxz .fail jmp @b @@: bt dword[esp],10 jnc @f neg edx lea edi,[edi+2+edx]; switch result to be always src's head relative @@: sub edi,[src] mov eax,edi jmp .exit .fail: xor eax,eax .exit: popfd ret endp
самым распространенным наверно будет алгоритм Бойера-Мура. хотя мне вот интересно, что в известных текстовых редакторах используется.
Ustus В отличии от scasb, где строка сканируется по-байтно, Бойер-Мур сканирует строку кусками, равными по длине подстроки -- выигрыш в скорости, а так полностью согласен с KeSqueer комбинация "repne scasb+repe cmpsb" в цикле выловит все возможные варианты
2010_07_14 таким образом callBack делает, чего ей хочется ... .if [callBack]<>0 call [callBack] ; thus callBack-the proc can do all ever .end if ...
недавно написал алгоритм Бойера-Мура-Хорспула (упрощенный вариант Бойера-Мура без суффиксной эвристики). кому интересно, можете заоптимизировать. например, как max7C4 в соседней теме оптимизировал примитивный алгоритм поиска подстроки http://wasm.ru/forum/viewtopic.php?id=36135 Код (Text): int substr_horspool(char* haystack, char* needle) { int i,j,k; int Lh = strlen(haystack); int Ln = strlen(needle); int T[256]; for(i=0; i<256; ++i) T[i] = Ln; for(i=0; i<Ln-1; ++i) { k = (unsigned char)needle[i]; T[k] = Ln-i-1; } for(i=Ln-1; i<Lh; (k==Ln-1) ? i+=T[(unsigned char)haystack[i]] : ++i) { for(j=i,k=Ln-1; k>=0; --j,--k) { if(haystack[j] != needle[k]) break; } if(k<0) break; } return (k<0) ? i-Ln+1 : -1; }
Вот СкопиПастил со своего проекта (немного упростил). Надеюсь работает. Код (Text): ;edi - адрес начала строки в которой ищем ;edx - длина строки в которой ищем ;szHL - адрес начала строки для поиска в сегменте .data ;[sizeHL] - длина строки для поиска .while edx>0 mov ecx, [sizeHL] xor eax,eax .while ecx xor al, [edi+ecx-1] ; xor al, [szHL+ecx-1] or ah, al dec ecx .endw .if ah==0 ; строка найдена .endif dec edx .endw
KeSqueer Э... возможно, я неправильно понял, как именно scasb+repe cmpsb... Может если увижу живой код, станет легче? Mikl___ Ну, не совсем так... преимущество Бойера-Мура в том, что он однопроходный, а при тупом сканировании придется делать откат. А сканировать все равно придется байтами, как же иначе??? (я не беру на рассмотрение всякие полухакерские ускорения )
edemko Не совсем, но близко Идею имел ввиду именно такую - работать в 32 разряда. Только вот Бойера-Мура в такой оптимизации сходу замутить - нужен талант Большого Темного Зеркала мне так вот сходу слабо А еще строковые операции - тот еще тормоз, лучше через mov.
