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

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

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

Так что добро пожаловать и приятного вам общения!!! ;)
 
Модераторы: 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 @
      чтобы он выводил все подстроки (слова) данной строки, которые одинаковы для обеих строк

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

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

            P.S. Понятно, что лучше городить макросы, но как это делать для таких динозавров я давно и основательно позабыл :-?
            Сообщение отредактировано: APleskan -
              Это будет совсем другой код :)
              В общих чертах: перебираешь каждое слово первой строки и ищешь эти слова во второй. Если нашёл, выводишь :)
              user posted image Чат форума в Telegramuser posted image Чат форума в Discord (жми и подключайся!) ;)
                Насколько я понимаю, без разбиения на отдельные процедуры здесь не обойтись?
                  Я бы сделал так:
                  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) + пробел.
                  user posted image Чат форума в Telegramuser posted image Чат форума в Discord (жми и подключайся!) ;)
                    Спасибо за наводку. Попробую довести до ума ;)
                      M

                      APleskan, кстати, тему надо называть не креативно, как роман, а соответственно сути вопроса!
                      user posted image Чат форума в Telegramuser posted image Чат форума в Discord (жми и подключайся!) ;)
                        На процедуры можно, конечно, не бить - но лапша же получится...

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

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

                          У меня обширная электронная библиотека. Есть еще Ирвин Кип, ;) так что, в любом случае чего-нибудь да сварганю :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
                              ?
                              Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
                              Есть претензии ко мне как к участнику? да ради бога.
                              Не нравятся мои ответы? не читайте их.
                              В общем, берегите себя. Нервные клетки не восстанавливаются.
                                Можно смоделировать 2-х проходной алгоритм:

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

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

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


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

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

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

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

                                                    Добавлено
                                                    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, вроде нужно было вывести одинаковые слова в двух строках, а не кол-во вхождений одной строки в другую... нет? :)
                                                      user posted image Чат форума в Telegramuser posted image Чат форума в Discord (жми и подключайся!) ;)
                                                        Поскольку в методичке у заказчика строгой формулировки размера входных данных не было, то я пошел на это жульничество :blush:

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

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

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


                                                                Рейтинг@Mail.ru
                                                                [ Script Execution time: 0,2617 ]   [ 17 queries used ]   [ Generated: 27.04.18, 08:26 GMT ]