Сборник по задачам и примерам Assembler
         

Прямой поиск в текстовой строке

«Корень зла есть незнание истины», — сказал Будда.
Из этого же корня вырастает дерево заблуждения
со своими тысячными плодами страдания.

Цель поиска некоторой строки Р в строке большего размера S — определить первый индекс элемента в строке S, начиная с которого все символы S совпадают с символами строки Р. Для этого алгоритм поиска последовательно просматривает символы строки S, проводя одновременное сравнение ее очередного символа с первым символом строки Р. После возникновения такого совпадения алгоритм производит последовательное сравнение соответствующих элементов строк S и Р до возникновения одного из следующих условий:

  • в процессе поиска соответствия достигнут конец строки Р — это означает,
    что строка Р совпадает с некоторой подстрокой строки S;
  • достигнут конец строки S при незавершенном или неначатом просмотре строки Р — это означает, что строка Р не соответствует ни одна из подстрок S.

Одна из главных проблем, которую приходится решать при написании программы обработки символьной строки, — определение конца строки S. Здесь возможны два варианта:

  • статический — размер строки фиксирован некоторым значением N;
  • динамический (характерен для обработки массивов символьных строк) — длина строки определяется значением, являющимся либо первым элементом очередной строки, либо концевым (служебным) символом, значение которого заранее определено и не может совпадать ни с одним символом строки.

Начнем обсуждение прямого способа поиска с программы поиска в строке с фиксированной длиной. Для экономии места ограничим число вхождений Р в S рдним.

;prg4_67_f.asm - поиск строки Р в строке S, Длина S фиксирована.
;Вход: S и Р - массивы символов размером N и М байт (М=<N.
:Выход: сообщение о количестве вхождений строки Р в строку S.
'.data"


:задаем массив S
s db "Ax. какой был яркий день! Лодка, солнце, блеск и тень, и везде цвела сирень."
Len_S=$-s
Db "$" mes db "Вхождений строки - "
:задаем массив Р - аргумент поиска
р db "ень"
1_еп_Р=$-р
db " - " Count (Jb 0."$" :счетчик вхождений Р a S
.code
eld
movcx.len_s
lea di ,s
moval ,p ;P[0]->al next_search:
lea si,p
incsi ;на следующий символ repne scasb
jcxz exit push ex
mov cx.len_p-l repe empsb
jz eq_substr :строка p <> подстроке в s
mov bx.len_p-l
sub bx.cx pop ex
subcx.bx ;учли пройденное при сравнении empsb
jmp next_search eq_substr:
;далее можно выйти, если поиск однократный, но мы упорные, поэтому продолжаем... рорех
sub сх.1еп_р-1 ;учли пройденное при сравнении empsb
inc count
jmp next_search exit: add count,30h :вывод сообщения mes на экран

Из программы видно, что когда размер строки фиксирован, то проблема конца строки решается просто. Но чаще приходится иметь дело с задачами, выполняющими поиск подстроки в строке, длина которой заранее не известна. Это характерно, в частности, для приложений обработки файлов. Но и с файлами не так все просто. Для текстовых ASCII-файлов особых проблем нет — в них строки заканчиваются символами Odh, Oah. Сложнее дело обстоит с обработкой двоичных файлов, где с равной степенью вероятности могут встретиться любые символы кодовой таблицы. В подобных случаях проблему локализации места в файле, где осуществляется поиск, нужно решать исходя из постановки конкретной задачи. Несмотря на это, сами приемы поиска не сильно отличаются от рассмотренных в этом разделе.
В случае когда поиск осуществляется в строке или в массиве строк в памяти, длина которых заранее не известна, то для обозначения их окончаний нужно ввести некоторый служебный символ. Например, в языке Паскаль существует понятие строки ASCII-Z, представляющей собой обычную символьную строку с завершающим нулевым символом. По этому символу и определяется конец строки. Подобные служебные символы можно использовать и для обработки строк
¦ в памяти. Другая возможность задания границы строки — введение в структуру строки специального байта, обычно первого, содержащего длину этой строки.
Следующая программа демонстрирует возможную организацию поиска в текстовом файле. Для этого содержимое файла читается в динамически выделяемую область памяти. После небольшой модернизации данную программу можно рассматривать как основу для других программ поиска в строках памяти, ограниченных некоторым служебным символом, как это обсуждалось выше. Программа производит поиск слова «шалтай» в строках файла. На экран выводится номер строки, в которой встретилось это слово, и количество повторений этого слова в файле. В такой постановке задачи возникает проблема — необходимо отслеживать наступление одного из двух событий: обнаружение первого символа образца или обнаружение первого из пары символов OdOah, обозначающих конец строки. Вариант использования цепочечных команд из предыдущей программы не подходит, так как сканировать строку можно на предмет наличия только одного символа. Поэтому данную задачу можно реализовать двумя способами. Первый способ заключается в последовательном чтении и проверке каждого символа строки на предмет удовлетворения их одному из обозначенных выше событий. При втором способе каждая строка файла сканируется два раза. На первом проходе определяется размер очередной строки, а затем эта строка сканируется второй раз на предмет наличия в ней искомой подстроки. Достоинство второго способа состоит в том, что его можно реализовать только использованием цепочечных команд. Какой из способов будет работать быстрее, можно определить с помощью профайлера. Мы выберем второй способ по двум причинам: во-первых, в этом разделе нас интересуют варианты использования цепочечных команд; во-вторых, в одной программе мы продемонстрируем приемы работы со строкой, размер которой определяется динамически двумя способами: со служебным символом в конце (им будет Odh) и извлекаемым из байта в начале строки. В нашей программе байт со значением длины очередной строки будет эмулироваться первым проходом.

start proc near :точка входа в программу:
;для размещения файла используем кучу, выделяемую процессу по умолчанию (1 Мбайт)
;HANDLE GetProcessHeap (VOID);
call GetProcessHeap
inov Hand_Head.eax сохраняем дескриптор ;читаем файл в динамически выделяемую область памяти ;открываем файл
:HANDLE CreateFiIeCLPCTSTR ipFileName.DWORD dwDesiredAccess.DWORD ;dwShareMode.LPSECURITY_ATTRIBUTES 1pSecuri tyAttributes.DWORD
:dwCreationDisposition.DWORD :dwFlagsAndAttributes.HANDLE hTemplateFi1e):
call CreateFileA
cmp eax.Offffffffh
je exit :если неуспех
mov hFile.eax :дескриптор файла определим размер файла :DWORD GetFi1eSize(HANDLE hFile.LPDWORD ipFileSizeHigh);
call GetFileSize
cmp eax.O
jz exit :если неуспех
mov FileSize.eax :сохраним размер файла :запрашиваем блок памяти из кучи:
:LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes): ;.........
call HeapAlloc
mov buf_start,eax :адрес блока с текстом программы из общей кучи процесса :читаем файл
:BOOL ReadFile(HANDLE hFile.LPVOID ipBuffer.DWORD nNumberOfBytesToRead. ;LPDWORD lpNumberOfBytesRead.LPOVERLAPPED lpOverlapped):
:.........
call ReadFile
cmp eax.O
jz exit :если неуспех push ds pop es
eld
mov ecx.FileSize
movedi.buf_start :адрес буфера с текстом файла в edi cycll: push ecx push edi
mov ebx.ecx
moval.Odh :0dh ->al repne scasb
jcxz e_exit
jmp $+7 e_exit: jmp exit pop edi
sub ebx.ecx
xchg ebx.ecx
mov al.p :P[0]->al next_search: repne scasb
jcxz end_str:достигнут конец строки проверяем возможное совпадение
push ecx lea esi.p
mov ecx.len_p-l repe empsb
jz eq_substr :строка р <> подстроке в s
mov edx.len_p-l
sub edx.ecx
sub ecx.edx :учли пройденное при сравнении empsb
jmp next_search end_str: incedi
xchg ebx.ecx преобразуем в символьное представление счетчик вхождений count
:вывод на экран строки mes call WriteConsoleA
mov count.0 обнуляем счетчик вхождений в строку pop ecx :1 - восстанавливаем
sub ecx.len_p-учли пройденное при сравнении empsb
inc count
jmp next_search
exit: pop ecx

;выход из программы - задержим ввод до нажатия любой клавиши
Этой программой мы проиллюстрировали оба варианта поиска с динамическим определением размера строки.
Алгоритмы, реализованные в этих программах, можно использовать для организации поиска в строке S небольшой длины, так как попытки повысить эффективность приведут к излишним накладным расходам. Для строки S большой размерности (потоковые данные для приложений мультимедиа) прямые алгоритмы поиска могут быть неэффективными. Положение можно исправить рассмотренными ниже алгоритмами поиска с предварительным анализом искомой подстроки.


Содержание раздела






Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий