0 / 0 / 0
Регистрация: 16.02.2017
Сообщений: 4
1

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

16.06.2017, 20:39. Показов 3326. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Необходимо написать программу на ассемблере которая будет выполнять поиск строки в тексте по алгоритму рабина - карпа , помогите , братья программисты )
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.06.2017, 20:39
Ответы с готовыми решениями:

Алгоритм Рабина-Карпа
Всем привет. Почему у меня Алгоритм Рабина - Карпа работает только для подстроки которая входит...

Алгоритм Рабина-Карпа
Всем доброго времени суток! Имеется код Алгоритма Рабина-Карпа, поиск подстроки в строке. Сегодня...

Алгоритм Рабина Карпа
Здравствуйте форумчане, снова нуждаюсь в помощи. Помогите реализовать одну вещь алгоритмом...

Алгоритм Карпа-Рабина
В общем не могу понять почему не подсчитывает кол-во вхождений подстроки в строку. using System;...

5
0 / 0 / 0
Регистрация: 16.02.2017
Сообщений: 4
24.06.2017, 03:46  [ТС] 2
Закройте эту тему , пожалуйста .
0
Модератор
Эксперт по электронике
8484 / 4342 / 1643
Регистрация: 01.02.2015
Сообщений: 13,484
Записей в блоге: 8
24.06.2017, 15:17 3
Лучший ответ Сообщение было отмечено Skydead как решение

Решение

Сам алгоритм несложный. Немного изменив алгоритм из 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
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
1
0 / 0 / 0
Регистрация: 16.02.2017
Сообщений: 4
24.06.2017, 22:54  [ТС] 4
Спасибо большое за код , я уверен что он рабочий , но не пойму , сделал exeшник через tasm , а она сразу показывается и закрывается , то есть ничего не успеваю увидеть в консоли, может быть я не через тот компилятор это делаю?
0
Модератор
Эксперт по электронике
8484 / 4342 / 1643
Регистрация: 01.02.2015
Сообщений: 13,484
Записей в блоге: 8
24.06.2017, 23:10 5
В строке 33 добавьте ожидание нажатия клавиши
Assembler
33
34
        mov     ah,     08h
        int     21h
1
0 / 0 / 0
Регистрация: 16.02.2017
Сообщений: 4
24.06.2017, 23:50  [ТС] 6
Отлично , все работает , спасибо большое еще раз, вы меня спасли!
0
24.06.2017, 23:50
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.06.2017, 23:50
Помогаю со студенческими работами здесь

Алгоритм Рабина-Карпа поиск строки в подстроке на Си
Помогите пожалуйста нужно сделать поиск подстроки в строке из файла с помощью алгоритма...

Алгоритм Рабина-Карпа, нужны комментарии к коду
Привет всем. Столкнулся с задачей разобраться с кодом алгоритма рабина карпа. Объясните пожалуйста...

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице
У меня есть этот алгоритм. Кто знает, как усовершенствовать его, чтобы он искал символьную...

Поиск подстроки в строке: алгоритм Рабина-Карпа или Бойера-Мура(-Хорспула)
Необходимо реализовать алгоритм Рабина-Карпа или Бойера-Мура(-Хорспула), если нам дана подстрока,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru