Алгоритм Рабина-Карпа

@Skydead · Регистрация: 16.02.2017

Author24 — интернет-сервис помощи студентам

Необходимо написать программу на ассемблере которая будет выполнять поиск строки в тексте по алгоритму рабина - карпа , помогите , братья программисты )

@Skydead · 24.06.2017, 03:46 **[ТС]**

Закройте эту тему , пожалуйста .

ФедосеевПавел · 24.06.2017, 15:17

Сам алгоритм несложный. Немного изменив алгоритм из Wikipedia - https://ru.wikipedia.org/wiki/... на_—_Карпа
получаю в псевдокоде
для текста T длиною TLen и строки поиска S длиною SLen (причём TLen>=SLen)

Код

SHash:=HashCalc(S[1..SLen])
for i from 1 to (TLen-SLen+1)
    THash := HashCalc(T[i..i+SLen-1])
    if SHash=THash
        if T[i..i+SLen-1]=S
            return i
return not_found

Здесь решение просто "в лоб", без оптимального получения нового хэша на основе предыдущего. Только, чтобы продемонстрировать алгоритм.

Assembler

LOCALS
 
.model small
 
.stack 100h
 
.data
        CrLf    db      0Dh, 0Ah, '$'
        NOT_FOUND       equ     -1
        ;текст
        T       db      'text string'
        TLen    dw      $-T
        ;строка
        S       db      'ext'
        SLen    dw      $-S
        ;
        THash   dw      ?
        SHash   dw      ?
.code
 
main    proc
        mov     ax,     @data
        mov     ds,     ax
 
        call    RabinKarp
 
        cmp     si,     NOT_FOUND
        je      @@NotFound
@@Found:
        mov     cx,     [SLen]
        call    ShowSubStr
@@NotFound:
 
        mov     ax,     4C00h
        int     21h
main    endp
 
RabinKarp       proc
        lea     si,     [S]             ;SHash := HashCalc(S[1..SLen])
        mov     cx,     [SLen]
        call    HashCalc
        mov     [SHash],        ax
        lea     si,     [T]             ;THash := HashCalc(T[1..SLen])
        mov     cx,     [SLen]
        call    HashCalc
        mov     [THash],        ax
 
        mov     cx,     TLen            ;for i from 1 to (TLen-SLen+1)
        sub     cx,     SLen
        inc     cx
 
        lea     si,     [T]             ;для вычисления THash := HashCalc(T[i..i+SLen-1])
 
@@For:
        push    cx
        mov     cx,     [SLen]          ;    THash := HashCalc(T[i..i+SLen-1])
        call    HashCalc
        mov     [THash],        ax
        pop     cx
        mov     ax,     [SHash]         ;    if SHash=THash
        cmp     ax,     [THash]
        jne     @@Next
 
        push    cx                      ;        if T[i..i+SLen-1]=S
        push    es
        push    si
        push    di
        mov     ax,     ds
        mov     es,     ax
        lea     di,     [S]             ;            return i
        mov     cx,     [SLen]
        repe    cmpsb
        pop     di
        pop     si
        pop     es
        pop     cx
        je      @@Break
@@Next:
        inc     si
        loop    @@For
        mov     si,     NOT_FOUND       ;return not found
@@Break:
        ret
RabinKarp       endp
 
;вычисление хэша для строки
;на входе:
;  ds:si - адрес строки
;  cx    - длина строки
;на выходе:
;  ax    - значение хэша
HashCalc        proc
        push    si
        push    cx
        pushf
 
        mov     ax,     0
@@HashLoop:
        shl     ax,     1
        add     al,     [si]
        adc     ah,     0
        add     si,     1
        loop    @@HashLoop
 
        popf
        pop     cx
        pop     si
        ret
HashCalc        endp
 
;процедура вывода подстроки
;на входе:
;  ds:si - адрес первого символа подстроки
;  cx    - длина выводимой подсторки
ShowSubStr      proc
        push    ax
        push    bx
        push    cx
        push    dx
        mov     ah,     40h
        mov     bx,     1
        mov     cx,     cx
        mov     dx,     si
        int     21h
        pop     dx
        pop     cx
        pop     bx
        pop     ax
        ret
ShowSubStr      endp
 
end     main

@Skydead · 24.06.2017, 22:54 **[ТС]**

Спасибо большое за код , я уверен что он рабочий , но не пойму , сделал exeшник через tasm , а она сразу показывается и закрывается , то есть ничего не успеваю увидеть в консоли, может быть я не через тот компилятор это делаю?

ФедосеевПавел · 24.06.2017, 23:10

В строке 33 добавьте ожидание нажатия клавиши

Assembler

33
34

        mov     ah,     08h
        int     21h

@Skydead · 24.06.2017, 23:50 **[ТС]**

Отлично , все работает , спасибо большое еще раз, вы меня спасли!

@Skydead 0 / 0 / 0 Регистрация: 16.02.2017 Сообщений: 4
		1
	Алгоритм Рабина-Карпа 16.06.2017, 20:39. Показов 3411. Ответов 5 Метки нет (Все метки) Необходимо написать программу на ассемблере которая будет выполнять поиск строки в тексте по алгоритму рабина - карпа , помогите , братья программисты ) 0

@Skydead 0 / 0 / 0 Регистрация: 16.02.2017 Сообщений: 4
	24.06.2017, 03:46 [ТС]	2
	Закройте эту тему , пожалуйста . 0

@Skydead 0 / 0 / 0 Регистрация: 16.02.2017 Сообщений: 4
	24.06.2017, 22:54 [ТС]	4
	Спасибо большое за код , я уверен что он рабочий , но не пойму , сделал exeшник через tasm , а она сразу показывается и закрывается , то есть ничего не успеваю увидеть в консоли, может быть я не через тот компилятор это делаю? 0

@Skydead 0 / 0 / 0 Регистрация: 16.02.2017 Сообщений: 4
	24.06.2017, 23:50 [ТС]	6
	Отлично , все работает , спасибо большое еще раз, вы меня спасли! 0

Алгоритм Рабина-Карпа

Решение