请在8086汇编条件下生成kmp算法的程序,其中字符串可以输入
时间: 2023-12-06 08:39:46 浏览: 173
以下是8086汇编条件下生成的KMP算法程序,其中字符串由用户输入:
```
.model small
.stack 100h
.data
pattern db 'abcde' ; 要匹配的模式
pattern_len equ $-pattern ; 模式长度
input_msg db '请输入需要匹配的字符串:$'
matched_msg db '匹配成功!$'
not_matched_msg db '未匹配成功!$'
.code
main proc
mov ax, @data
mov ds, ax
; 打印提示信息,要求用户输入字符串
mov ah, 09h
lea dx, input_msg
int 21h
; 读入用户输入的字符串
mov ah, 0ah
lea dx, input_buffer
int 21h
; 将回车换行替换为字符串结束符
mov si, dx
add si, word ptr [si+1] ; 求出字符串长度
mov bl, 0dh ; 回车
mov bh, 00h
mov byte ptr [si-2], '$' ; 将回车换为字符串结束符
cmp byte ptr [si-3], bl ; 如果最后一个字符是换行,则将换行也换为字符串结束符
je end_input
add byte ptr [si-1], 1 ; 字符串长度加1
end_input:
mov dx, offset input_buffer
; 调用KMP算法进行匹配
call kmp_match
; 输出匹配结果
cmp byte ptr [matched], 1
jne not_matched
matched:
mov ah, 09h
lea dx, matched_msg
int 21h
jmp end_prog
not_matched:
mov ah, 09h
lea dx, not_matched_msg
int 21h
end_prog:
mov ah, 4ch
int 21h
; KMP算法匹配函数
kmp_match proc
push bx
push cx
push dx
push si
push di
; 初始化next数组
mov cx, pattern_len
xor di, di ; next数组下标
mov byte ptr [next+di], 0 ; next[0] = 0
mov bx, 0 ; 模式串的前缀指针
next_loop:
cmp bx, cx ; 如果前缀指针已经到达模式串末尾,跳出循环
je match
mov al, pattern[bx] ; 取出字符
mov ah, pattern[di] ; 取出next数组对应位置的字符
cmp al, ah
je next_match
next_mismatch:
mov ah, pattern[di] ; 取出next数组对应位置的字符
cmp ah, 0 ; 如果next数组的值为0,跳到match
je match
mov di, byte ptr [next+di] ; 回溯到next数组的上一个位置
jmp next_mismatch
next_match:
inc bx ; 前缀指针后移
inc di ; next数组下标后移
mov cl, byte ptr [next+di-1] ; 取出前一个位置的next值
cmp al, pattern[cl] ; 如果当前字符等于前一个位置的字符,则next[i] = next[i-1] + 1
je next_match_eq
next_match_neq:
mov byte ptr [next+di], cl ; next[i] = next[i-1]
jmp next_loop
next_match_eq:
inc cl
mov byte ptr [next+di], cl ; next[i] = next[i-1] + 1
jmp next_loop
match:
; 匹配字符串
xor dx, dx ; dx为匹配位置指针
mov si, dx ; si为输入字符串指针
mov bx, 0 ; bx为模式串指针
match_loop:
cmp bx, pattern_len ; 如果已经匹配到模式串末尾,则匹配成功
je match_success
cmp byte ptr [dx+si], pattern[bx] ; 如果匹配失败,则回溯
jne match_fail
inc bx ; 模式串指针后移
inc dx ; 匹配位置指针后移
jmp match_loop
match_success:
mov byte ptr [matched], 1 ; 标记匹配成功
jmp match_end
match_fail:
cmp byte ptr [next+bx], 0 ; 如果next数组的值为0,则回溯到input_buffer的下一个位置
je fail_next
mov bx, byte ptr [next+bx] ; 回溯到next数组的上一个位置
jmp match_loop
fail_next:
inc si ; 回溯到input_buffer的下一个位置
mov dx, si ; 匹配位置指针指向input_buffer的下一个位置
mov bx, 0 ; 模式串指针指向模式串的第一个位置
jmp match_loop
match_end:
pop di
pop si
pop dx
pop cx
pop bx
ret
matched db 0 ; 标记匹配结果
input_buffer db 80, ?, 80 dup(0) ; 用户输入的字符串
next db pattern_len dup(0) ; next数组
kmp_match endp
end main
```
注意事项:
- 在本程序中,模式串为`abcde`,可以根据需要修改。
- 程序中使用了`int 21h`来进行输入输出操作,因此需要在DOS或DOSBox等环境下运行。
阅读全文