Обработка цепочек элементов
Прямой поиск в текстовой строке
"Корень зла есть незнание истины", – сказал Будда.
Из этого же корня вырастает дерево заблуждения
со своими тысячными плодами страдания.
Цель поиска некоторой строки Р в строке большего размера 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, представляющей собой обычную символьную строку с завершающим нулевым символом. По этому символу и определяется конец строки. Подобные служебные символы можно использовать и для обработки строк в памяти. Другая возможность задания границы строки – введение в структуру строки специального байта, обычно первого, содержащего длину этой строки.
Следующая программа демонстрирует возможную организацию поиска в текстовом файле. Для этого содержимое файла читается в динамически выделяемую область памяти. После небольшой модернизации данную программу можно рассматривать как основу для других программ поиска в строках памяти, ограниченных некоторым служебным символом, как это обсуждалось выше. Программа производит поиск слова "шалтай" в строках файла. На экран выводится номер строки, в которой встретилось это слово, и количество повторений этого слова в файле.