Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.213.110.162] |
|
Сообщ.
#1
,
|
|
|
Всем привет!
Есть код из книги Юрова по ассемблеру ;prg_12_4.asm MASM MODEL small STACK 256 .data ;строки для сравнения string1 db 'Поиск символа в этой строке.',0ah,0dh,'$' string2 db 'Поиск символа не в этой строке.',0ah,0dh,'$' mes_eq db 'Строки совпадают.',0ah,0dh,'$' fnd db 'Несовпавший элемент в регистре al',0ah,0dh,'$' .code ;привязка ds и es к сегменту данных assume ds:@data,es:@data main: mov ax,@data ;загрузка сегментных регистров mov ds,ax mov es,ax ;настройка es на ds mov ah,09h lea dx,string1 int 21h ;вывод string1 lea dx,string2 int 21h ;вывод string2 cld ;сброс флага df lea di,string1 ;загрузка в es:di смещения ;строки string1 lea si,string2 ;загрузка в ds:si смещения ;строки string2 mov cx,29 ;для префикса repe - длина строки ;поиск в строке (пока нужный символ и символ в строке не равны) ;выход - при первом несовпавшем repe cmps string1,string2 jcxz eql ;если равны - переход на eql jmp no_eq ;если не равны - переход на no_eq eql: ;выводим сообщение о совпадении строк mov ah,09h lea dx,mes_eq int 21h ;вывод сообщения mes_eq jmp exit ;на выход no_eq: ;обработка несовпадения элементов mov ah,09h lea dx,fnd int 21h ;вывод сообщения fnd ;теперь, чтобы извлечь несовпавший элемент из строки ;в регистр-аккумулятор, ;уменьшаем значение регистра si и тем самым перемещаемся ;к действительной позиции элемента в строке dec si ;команда lods использует ds:si-адресацию ;теперь ds:si указывает на позицию в string2 lods string2 ;загрузим элемент из строки в AL ;нетрудно догадаться, что в нашем примере это символ - "н" exit: ;выход mov ax,4c00h int 21h end main Результатом его работы является первая символ (подстрока), который не совпадает со строкой образцом. Он заносится в регистр AL, это понятно. А как нужно изменить данный код таким образом, чтобы он выводил все подстроки (слова) данной строки, которые одинаковы для обеих строк? Не соображу |
Сообщ.
#2
,
|
|
|
Цитата APleskan @ чтобы он выводил все подстроки (слова) данной строки, которые одинаковы для обеих строк Нипанятна... покажите хотя бы эталонный вывод для строк из кода. |
Сообщ.
#3
,
|
|
|
Проще говоря нужно сравнить две строки на предмет нахождения в них одинаковых слов.
Вот так |
Сообщ.
#4
,
|
|
|
Понятнее не стало. Покажи, что хочешь получить на экране, если в код внести нужные тебе исправления.
В текущем виде при запуске должно получиться нечто вроде: c:\> prg_12_4 Поиск символа в этой строке. Поиск символа не в этой строке. Несовпавший элемент в регистре al c:\> |
Сообщ.
#5
,
|
|
|
Этот выхлоп есть. Нужно получить, например, для двух строк: красное яблоко и зелёное яблоко результат яблоко.
P.S. Понятно, что лучше городить макросы, но как это делать для таких динозавров я давно и основательно позабыл |
Сообщ.
#6
,
|
|
|
Это будет совсем другой код
В общих чертах: перебираешь каждое слово первой строки и ищешь эти слова во второй. Если нашёл, выводишь |
Сообщ.
#7
,
|
|
|
Насколько я понимаю, без разбиения на отдельные процедуры здесь не обойтись?
|
Сообщ.
#8
,
|
|
|
Я бы сделал так:
String1 db 'Hello my big boss!',0 String2 db 'Good bye my little boss!',0 First dw String1 Second dw String2 И дальше нужна процедура NextWord, которая переходит к следующему слову (в регистре BX, скажем, ей передаётся адрес переменной с текущей позицией строки), т.е.: CompareNext: . . . lea bx,First call NextWord jnc CompareNext . . . NextWord proc mov si,[bx] . . . Ну и нужна будет функция, сравнивающая оба слова (из First и Second) и ещё процедура, выводящая текущее слово (из First) + пробел. |
Сообщ.
#9
,
|
|
|
Спасибо за наводку. Попробую довести до ума
|
Сообщ.
#10
,
|
|
|
M APleskan, кстати, тему надо называть не креативно, как роман, а соответственно сути вопроса! |
Сообщ.
#11
,
|
|
|
На процедуры можно, конечно, не бить - но лапша же получится...
И учти, что для каждого слова первой строки тебе надо будет проверять совпадение со всеми словами второй строки. Так что начни с написания процедуры поиска одного слова в строке, а потом добавишь обвязку перебора слов. И для упрощения я бы сначала в обеих строках заменил все разделители слов на некий один и тот же символ, который в строке гарантированно отсутствует. Совсем отлично, если это будет символ доллара - упростит вывод. |
Сообщ.
#12
,
|
|
|
Всем спасибо за ответы.
У меня обширная электронная библиотека. Есть еще Ирвин Кип, так что, в любом случае чего-нибудь да сварганю Добавлено Кстати да, я старею. У того же Юрова в "Практикуме" есть решение похожей задачи Jin X можете сносить тред |
Сообщ.
#13
,
|
|
|
Оставлю здесь частное решение задачи, авось кому-то пригодится
;--------------------------------------------------------------------------------; ;search.asm - поиск строки P в строке S. Длина S фиксирована. ;Вход: S и P - массивы символов размером N и M байт (M=<N). ;Выход: сообщение о количестве вхождений строки P в строку S. ;--------------------------------------------------------------------------------; masm model small .data ;задаем массив S s db "яблоко красное, зеленое яблоко, яблоко сладкое, кислое яблоко, яблоко летнее, спелое яблоко" Len_S=$-s Db "$" mes db "Вхождений строки - " ;задаем массив P - аргумент поиска p db "зеленое яблоко" Len_P=$-p db " - " Count db 0,"$" ;счетчик вхождений P в S .stack 256 .486 .code main: mov dx,@data mov ds,dx push ds pop es cld mov cx,len_s lea di,s mov al,p ;P[0]->al next_search: lea si,p inc si ;на следующий символ repne scasb jcxz exit push cx mov cx,len_p-1 repe cmpsb jz eq_substr ;строка p <> подстроке в s mov bx,len_p-1 sub bx,cx pop cx sub cx,bx ;учли пройденное при сравнении cmpsb jmp next_search eq_substr: ;далее можно выйти, если поиск однократный, но мы упорные, поэтому продолжаем pop cx sub cx,len_p-1 ;учли пройденное при сравнении cmpsb inc count jmp next_search exit: add count,30h ;преобразуем число в строку lea dx,mes mov ah,9h int 21h ;выход mov ax,4c00h int 21h end main Доработка приветствуется |
Сообщ.
#14
,
|
|
|
s db 15 dup("aa ") ... p db "aa" s db "ababac" ... p db "abaс" mov dx,@data mov ds,dx push ds pop es А почему не mov dx,@data mov ds,dx mov es,dx И за каким тут .486 |
Сообщ.
#15
,
|
|
|
Можно смоделировать 2-х проходной алгоритм:
1) Находится первый, последний символ текущего слова и расстояние (длина слова) в первой строке 2) Ищется тоже самое во второй строке 3) Если все совпадает - вторым проходом сравниваются слова на полное совпадение Во многих случаях - можно получить прирост скорости сравнения. Т.к. получается некое подобие сравнивания не данных, а такого вот примитивного хэша. Естественно - в некоторых случаях это может наоборот притормозить. Чуйка подсказывает, что для обработки естественного текста подход будет полезен. |
Сообщ.
#16
,
|
|
|
Фигня имхо. Я бы, упрись мне скорость, скорее думал бы в направлении сравнения словами.
|
Сообщ.
#17
,
|
|
|
REPE SCASB замечательно найдет пробел, а значит и предыдущий символ. Скорость данной конструкции превосходная.
|
Сообщ.
#18
,
|
|
|
Akina Согласен, но посколько у заказчика сего не было обозначено четких требований к формату входных данных, слепил как говорится из того, что было На досуге для себя может допилю таки. Хотя таких ископаемых динозавров как тасм давно пора оставить палеонтологам
Добавлено mov dx,@data mov ds,dx push ds pop es Ну дык стек надо подергать, че ему прохлажаться то?! Хотя если серьезно разбираю демо-примеры FASM DOS Гриштара я задавался тем же вопросом. Что это за стиль инициализировать сегмент данных через стек?! |
Сообщ.
#19
,
|
|
|
Цитата APleskan @ У меня в книжке "Программируем на языке ассемблера IBM PC" дословно эти строки так описаны:Что это за стиль инициализировать сегмент данных через стек?! Цитата В нашей программе эти строки не имеют практического смысла, но вообще здесь продемонстрирован удобный приём переноса содержимого одного сегментного регистра в другой. |
Сообщ.
#20
,
|
|
|
Цитата APleskan @ Что это за стиль инициализировать сегмент данных через стек?! Компактности ради - PUSH/POP однобайтные. Хотя по скорости копированию из РОН проигрывают. |
Сообщ.
#21
,
|
|
|
А там не случится, что современные ЦП увидят подряд push/pop и всё внутрях перенесут почти столь же быстро аки и из РОНа?
|
Сообщ.
#22
,
|
|
|
Akina, ясно понятно
|
Сообщ.
#23
,
|
|
|
Akina, т.е. по поводу второго, указанного Вами, недостатка нужно, например, сравнивать посимвольно на предмет совпадения каждый символ искомой подстроки с исходной строкой с 1-го символа исходной строки до ее конца, со второго до конца исходной строки и т.д.?
Конечно, получается совсем неэффективно с точки зрения алгоритма, но пока ничего другого в голову не пришло. Или есть лучшее решение? |
Сообщ.
#24
,
|
|
|
Цитата APleskan @ Или есть лучшее решение? Поиск слова в строке - двухэтапный. Сначала ищется первый символ, а при нахождении его - сравнивается посимвольно всё слово. Так вот - если второй этап неудачен, дальнейший скан по первому этапу следует проводить не с той точки. где закончился неудачный последний второй этап, а с той, где закончился последний первый этап. Т.е. указателей - два. И процедур соответственно две - первая ищет в одной строке заданный символ, вторая, вызываемая из первой, сравнивает два слова. И она же, если обнаружено совпадение, выполняет вывод. |
Сообщ.
#25
,
|
|
|
Понял. Но все равно, мы же не возвращаемся назад при сравнении? Просматриваем строку слева направо из начала в конец (до нуль-терминатора)
Добавлено Akina Бойер-Мур таки, вот это извращение ;--------------------------------------------------------------------------------; ;Вход: S и P - массивы символов размером N и M байт (M=<N). ;Выход: сообщение о количестве вхождений строки P в строку S. ;--------------------------------------------------------------------------------; masm model small .data mes db 0dh,0ah,"Вхождений строки - " ;задаем массив P - аргумент поиска p db "abac" Len_P=$-p ;M=Len_P db " - в строку - " ;задаем массив S s db "ababac" Len_S=$-s ;N=Len_S db " - " Count db 0 ;счетчик вхождений P в S Db " раз(а)$" d db 255 dup (0) ;вспомогательный массив k db 0 .stack 256 .code main: mov dx,@data mov ds,dx push ds pop es ;этап 1 - заполнение массива D ;заполняем элементы массива d значением M - размером образца для поиска mov cx,255 ;размер кодовой таблицы ASCII mov al,len_p lea di,d rep stosb ;цикл просмотра образца и замещение некоторых элементов d значениями смещений ;ДЛЯ j=0 ДО M-2 ДЕЛАТЬ ;НАЧ_БЛОК_1 ;d[p[j]]:=M-j-1 ;КОН_БЛОК_1 xor si,si ;j:=0 cycl1: cmp si,len_p-1 jge e_cycl1 mov al,p[si] mov di,ax mov bl,len_p dec bl sub bx,si mov d[di],bl inc si jmp cycl1 e_cycl1: ;//этап 2: поиск ;i:=M mov di,len_p ;I:=M ;ПОВТОРИТЬ ;j:=M; k:=i ;цикл пока (j>=0)ИЛИ(I<n) cycl2: mov si,len_p ;j:=M mov bx,di ;k:=I ;ПОВТОРИТЬ ;K:=k-1;j:=j-1 ;ПОКА (j>=0)ИЛИ(p[j]==s[k]) ;цикл пока (j>=0)ИЛИ(p[j]==p[k]) cycl3: dec bx ;k:=k-1 dec si ;j:=j-1 ;цикл пока (j>=0)ИЛИ(p[j]==p[k]) cmp si,0 jl m2 mov al,p[si] cmp s[bx],al jne m2 jmp cycl3 m2: ;i:=i+d[s[i-1]] push di dec di mov al,s[di] mov di,ax mov al,d[di] pop di add di,ax ;I:=I+d[s[I-1]] ;ПОКА (j>=0)ИЛИ(i<N) ;цикл пока (j>=0)ИЛИ(I<n) cmp si,0 jl m1 cmp di,len_s jg exit_f jmp cycl2 ;ЕСЛИ j<0 ТО вывод сообщения об удаче поиска ;ИНАЧЕ вывод сообщения о неудаче поиска m1: ;вывод сообщения о результатах поиска inc count jmp cycl2 exit_f: add count,30h lea dx,mes mov ah,09h int 21h exit: ;КОН_ПРОГ ;выход mov ax,4c00h int 21h end main Почти все уже |
Сообщ.
#26
,
|
|
|
APleskan, вроде нужно было вывести одинаковые слова в двух строках, а не кол-во вхождений одной строки в другую... нет?
|
Сообщ.
#27
,
|
|
|
Поскольку в методичке у заказчика строгой формулировки размера входных данных не было, то я пошел на это жульничество
Там задача была поставлена так: взять две произвольных строки, закинуть их в сегмент данных, "кипятить" до готовности. Говоря образно P.S. Но этот случай сподвиг меня разобраться, что же такое префикс-функция (на примерах из ЯВУ). P.P.S. Вывести одинаковые слова не проблема, проблема правильно сформулировать задачу из методички местечкового ВУЗа |
Сообщ.
#28
,
|
|
|
APleskan
Так какое твоё-то место во всей этой кухне? Студент, выполняющий задание? Преподаватель, создающий новую версию методички? Просто сочувствующий, решивший чёнить накодить на старом АСМе? или где? |
Сообщ.
#29
,
|
|
|
Имхо, фрилансер (окучивающий студентов местного вуза), который берется за то, что сам не умеет.
|
Сообщ.
#30
,
|
|
|
Лучше хоть что-то, чем вообще нихрена. Тем более, заказчик так и не рассчитался. Так что, все честно, на самом деле
|
Сообщ.
#31
,
|
|
|
мои "пять копеек"
1) первый проход в первой строке ищется разделитель слов "пробел" или "запятая" или "скобки" и т.п. или символ конца строки при этом создается база содержащая записи "адрес начала слова"+"длина слова" 2) второй проход то же самое, но со второй строкой база содержит"адрес начала слова"+"длина слова"+"счетчик совпадений" инициализированный нулями 3) сравниваем последовательно длины слов первой строки со второй строкой, если не совпали переходим к следующему слову, если длины совпали проверяем на совпадение символов, если совпали все символы инкрементируем "счетчик совпадений" 4) выводим на экран те слова, у которых "счетчик совпадений" не содержат нули |