На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Перед отправкой сообщения внимательно прочтите правила раздела!!!
1. Запрещается обсуждать написание вирусов, троянов и других вредоносных программ!
2. Помните, что у нас есть FAQ раздела Assembler и Полезные ссылки. Посмотрите, возможно, там уже имеется решение вашего вопроса.

3. Настоятельно рекомендуем обратить особое внимание на правила форума, которые нарушаются чаще всего:
  3.1. Заголовок темы должен кратко отражать её суть. Темы с заголовками типа "Срочно помогите!" или "Ассемблер" будут отправляться в Корзину для мусора.
  3.2. Исходники программ обязательно выделяйте тегами [code]...[/code] (одиночные инструкции можно не выделять).
  3.3. Нежелательно поднимать старые темы (не обновлявшиеся более года) без веской на то причины.

Не забывайте также про главные Правила форума!

Добро пожаловать и приятного вам общения!!! ;)
 
Модераторы: Jin X, Qraizer
  
> Поиск одинаковых слов в строках , Вопрос по TASM
    Всем привет!
    Есть код из книги Юрова по ассемблеру
    ExpandedWrap disabled
      ;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, это понятно.
    А как нужно изменить данный код таким образом, чтобы он выводил все подстроки (слова) данной строки, которые одинаковы для обеих строк?
    Не соображу :crazy:
      Цитата APleskan @
      чтобы он выводил все подстроки (слова) данной строки, которые одинаковы для обеих строк

      Нипанятна... покажите хотя бы эталонный вывод для строк из кода.
        Проще говоря нужно сравнить две строки на предмет нахождения в них одинаковых слов.
        Вот так :D
          Понятнее не стало. Покажи, что хочешь получить на экране, если в код внести нужные тебе исправления.

          В текущем виде при запуске должно получиться нечто вроде:
          ExpandedWrap disabled
            c:\> prg_12_4
             
            Поиск символа в этой строке.
            Поиск символа не в этой строке.
            Несовпавший элемент в регистре al
             
            c:\>
            Этот выхлоп есть. Нужно получить, например, для двух строк: красное яблоко и зелёное яблоко результат яблоко.
            :)

            P.S. Понятно, что лучше городить макросы, но как это делать для таких динозавров я давно и основательно позабыл :-?
            Сообщение отредактировано: APleskan -
              Это будет совсем другой код :)
              В общих чертах: перебираешь каждое слово первой строки и ищешь эти слова во второй. Если нашёл, выводишь :)
                Насколько я понимаю, без разбиения на отдельные процедуры здесь не обойтись?
                  Я бы сделал так:
                  ExpandedWrap disabled
                    String1 db 'Hello my big boss!',0
                    String2 db 'Good bye my little boss!',0
                    First dw String1
                    Second dw String2
                  First - текущая позиция строки String1, Second - строки String2.
                  И дальше нужна процедура NextWord, которая переходит к следующему слову (в регистре BX, скажем, ей передаётся адрес переменной с текущей позицией строки), т.е.:
                  ExpandedWrap disabled
                    CompareNext:
                      . . .
                      lea bx,First
                      call NextWord
                      jnc CompareNext
                    . . .
                    NextWord proc
                      mov si,[bx]
                    . . .
                  процедура будет переходить к следующему слову (т.е. пропускать сначала все буквенные символы, затем все небуквенные). Если встретит в итоге 0 (конец строки), вернёт флаг CF=1 (stc), иначе CF=0 (clc).

                  Ну и нужна будет функция, сравнивающая оба слова (из First и Second) и ещё процедура, выводящая текущее слово (из First) + пробел.
                    Спасибо за наводку. Попробую довести до ума ;)
                      M

                      APleskan, кстати, тему надо называть не креативно, как роман, а соответственно сути вопроса!
                        На процедуры можно, конечно, не бить - но лапша же получится...

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

                        И для упрощения я бы сначала в обеих строках заменил все разделители слов на некий один и тот же символ, который в строке гарантированно отсутствует. Совсем отлично, если это будет символ доллара - упростит вывод.
                          Всем спасибо за ответы.

                          У меня обширная электронная библиотека. Есть еще Ирвин Кип, ;) так что, в любом случае чего-нибудь да сварганю :rolleyes:

                          Добавлено
                          Кстати да, я старею. У того же Юрова в "Практикуме" есть решение похожей задачи 8-)
                          Jin X можете сносить тред :ph34r:
                            Оставлю здесь частное решение задачи, авось кому-то пригодится :)
                            ExpandedWrap disabled
                              ;--------------------------------------------------------------------------------;
                              ;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

                            Доработка приветствуется :thanks:
                              ExpandedWrap disabled
                                s db 15 dup("aa ")
                                ...
                                p db "aa"
                              Упс...

                              ExpandedWrap disabled
                                s db "ababac"
                                ...
                                p db "abaс"
                              Упс-2...

                              ExpandedWrap disabled
                                        mov     dx,@data
                                        mov     ds,dx
                                push    ds
                                pop     es

                              А почему не
                              ExpandedWrap disabled
                                        mov     dx,@data
                                        mov     ds,dx
                                        mov     es,dx
                              ?

                              И за каким тут
                              ExpandedWrap disabled
                                .486
                              ?
                                Можно смоделировать 2-х проходной алгоритм:

                                1) Находится первый, последний символ текущего слова и расстояние (длина слова) в первой строке
                                2) Ищется тоже самое во второй строке
                                3) Если все совпадает - вторым проходом сравниваются слова на полное совпадение

                                Во многих случаях - можно получить прирост скорости сравнения. Т.к. получается некое подобие сравнивания не данных, а такого вот примитивного хэша. Естественно - в некоторых случаях это может наоборот притормозить. Чуйка подсказывает, что для обработки естественного текста подход будет полезен.
                                  Фигня имхо. Я бы, упрись мне скорость, скорее думал бы в направлении сравнения словами.
                                    REPE SCASB замечательно найдет пробел, а значит и предыдущий символ. Скорость данной конструкции превосходная.
                                      Akina Согласен, но посколько у заказчика сего не было обозначено четких требований к формату входных данных, слепил как говорится из того, что было ;) На досуге для себя может допилю таки. Хотя таких ископаемых динозавров как тасм давно пора оставить палеонтологам :D

                                      Добавлено
                                      ExpandedWrap disabled
                                         mov     dx,@data
                                         mov     ds,dx
                                         push    ds
                                         pop     es


                                      Ну дык стек надо подергать, че ему прохлажаться то?!

                                      Хотя если серьезно разбираю демо-примеры FASM DOS Гриштара я задавался тем же вопросом. Что это за стиль инициализировать сегмент данных через стек?!
                                        Цитата APleskan @
                                        Что это за стиль инициализировать сегмент данных через стек?!
                                        У меня в книжке "Программируем на языке ассемблера IBM PC" дословно эти строки так описаны:
                                        Цитата
                                        В нашей программе эти строки не имеют практического смысла, но вообще здесь продемонстрирован удобный приём переноса содержимого одного сегментного регистра в другой.
                                        :rolleyes:
                                          Цитата APleskan @
                                          Что это за стиль инициализировать сегмент данных через стек?!

                                          Компактности ради - PUSH/POP однобайтные. Хотя по скорости копированию из РОН проигрывают.
                                            А там не случится, что современные ЦП увидят подряд push/pop и всё внутрях перенесут почти столь же быстро аки и из РОНа?
                                              Akina, ясно понятно :yes:
                                              Сообщение отредактировано: APleskan -
                                                Akina, т.е. по поводу второго, указанного Вами, недостатка нужно, например, сравнивать посимвольно на предмет совпадения каждый символ искомой подстроки с исходной строкой с 1-го символа исходной строки до ее конца, со второго до конца исходной строки и т.д.?
                                                Конечно, получается совсем неэффективно с точки зрения алгоритма, но пока ничего другого в голову не пришло. Или есть лучшее решение?
                                                  Цитата APleskan @
                                                  Или есть лучшее решение?

                                                  Поиск слова в строке - двухэтапный. Сначала ищется первый символ, а при нахождении его - сравнивается посимвольно всё слово. Так вот - если второй этап неудачен, дальнейший скан по первому этапу следует проводить не с той точки. где закончился неудачный последний второй этап, а с той, где закончился последний первый этап. Т.е. указателей - два. И процедур соответственно две - первая ищет в одной строке заданный символ, вторая, вызываемая из первой, сравнивает два слова. И она же, если обнаружено совпадение, выполняет вывод.
                                                    Понял. Но все равно, мы же не возвращаемся назад при сравнении? Просматриваем строку слева направо из начала в конец (до нуль-терминатора)

                                                    Добавлено
                                                    Akina Бойер-Мур таки, вот это извращение :lol:
                                                    ExpandedWrap disabled
                                                      ;--------------------------------------------------------------------------------;
                                                      ;Вход: 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


                                                    Почти все уже украдено до нас написано до нас :P
                                                    Сообщение отредактировано: APleskan -
                                                      APleskan, вроде нужно было вывести одинаковые слова в двух строках, а не кол-во вхождений одной строки в другую... нет? :)
                                                        Поскольку в методичке у заказчика строгой формулировки размера входных данных не было, то я пошел на это жульничество :blush:

                                                        Там задача была поставлена так: взять две произвольных строки, закинуть их в сегмент данных, "кипятить" до готовности.
                                                        Говоря образно :)

                                                        P.S. Но этот случай сподвиг меня разобраться, что же такое префикс-функция (на примерах из ЯВУ). А то Седжвик, зараза, уже не напишет главу о алгоритмах на строках Пошел читать Кормена :D

                                                        P.P.S. Вывести одинаковые слова не проблема, проблема правильно сформулировать задачу из методички местечкового ВУЗа
                                                        Сообщение отредактировано: APleskan -
                                                          APleskan
                                                          Так какое твоё-то место во всей этой кухне? Студент, выполняющий задание? Преподаватель, создающий новую версию методички? Просто сочувствующий, решивший чёнить накодить на старом АСМе? или где?
                                                            Имхо, фрилансер (окучивающий студентов местного вуза), который берется за то, что сам не умеет.
                                                            Сообщение отредактировано: shm -
                                                              Лучше хоть что-то, чем вообще нихрена. Тем более, заказчик так и не рассчитался. Так что, все честно, на самом деле :D
                                                              Сообщение отредактировано: APleskan -
                                                                мои "пять копеек"
                                                                1) первый проход в первой строке ищется разделитель слов "пробел" или "запятая" или "скобки" и т.п. или символ конца строки при этом создается база содержащая записи "адрес начала слова"+"длина слова"
                                                                2) второй проход то же самое, но со второй строкой база содержит"адрес начала слова"+"длина слова"+"счетчик совпадений" инициализированный нулями
                                                                3) сравниваем последовательно длины слов первой строки со второй строкой, если не совпали переходим к следующему слову, если длины совпали проверяем на совпадение символов, если совпали все символы инкрементируем "счетчик совпадений"
                                                                4) выводим на экран те слова, у которых "счетчик совпадений" не содержат нули
                                                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                                                0 пользователей:


                                                                Рейтинг@Mail.ru
                                                                [ Script execution time: 0,0744 ]   [ 16 queries used ]   [ Generated: 28.03.24, 21:37 GMT ]