用汇编语言实现模式算法

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAX_LEN_OF_STR 30 // 字符串的最大长度

typedef struct String // 这里需要的字符串数组,存放字符串及其长度
{
char str[MAX_LEN_OF_STR]; // 字符数组
int length; // 字符串的实际长度
}String, *PString;

// 得到字符串的next数组
void GetNextArray(PString pstr, int next[])
{
assert(NULL != pstr);
assert(NULL != next);
assert(pstr->length > 0);

// 第一个字符的next值是-1,因为C中的数组是从0开始的
next[0] = -1;
for (int i = 0, j = -1; i < pstr->length - 1; )
{
// i是主串的游标,j是模式串的游标
// 这里的主串和模式串都是同一个字符串
if (-1 == j || // 如果模式串游标已经回退到第一个字符
pstr->str[i] == pstr->str[j]) // 如果匹配成功
{
// 两个游标都向前走一步
++i;
++j;
// 存放当前的next值为此时模式串的游标值
next[i] = j;
}
else // 匹配不成功j就回退到上一个next值
{
j = next[j];
}
}
}

// KMP字符串模式匹配算法
// 输入: S是主串,T是模式串,pos是S中的起始位置
// 输出: 如果匹配成功返回起始位置,否则返回-1
int KMP(PString S, PString T, int pos)
{
assert(NULL != S);
assert(NULL != T);
assert(pos >= 0);
assert(pos < S->length);

if (S->length < T->length)
return -1;

printf("主串\t = %s\n", S->str);
printf("模式串\t = %s\n", T->str);

int *next = (int *)malloc(T->length * sizeof(int));
// 得到模式串的next数组
GetNextArray(T, next);

int i, j;
for (i = pos, j = 0; i < S->length && j < T->length; )
{
// i是主串游标,j是模式串游标
if (-1 == j || // 模式串游标已经回退到第一个位置
S->str[i] == T->str[j]) // 当前字符匹配成功
{
// 满足以上两种情况时两个游标都要向前进一步
++i;
++j;
}
else // 匹配不成功,模式串游标回退到当前字符的next值
{
j = next[j];
}
}

free(next);

if (j >= T->length)
{
// 匹配成功
return i - T->length;
}
else
{
// 匹配不成功
return -1;
}
}

.model small
.386
option casemap:none

data segment
i dw 0
j dw -1
next dw 30 dup(0)
success db 'Success!$'
fail db 'Failed!$'
data ends

String struc
len dw 0
str db 30 dup('')
String ends

code segment use16 ;这里加上use16非常重要，如果不加则无法显示结果
assume cs:code,ds:data
start:
mov ax,data
mov ds,ax
String S <>
String T <>
call KMP
mov ah,4ch
int 21h

KMP proc far
push si
push di
push bx
push ax
push cx
push dx
cmp S.len,T.len
jl rettt
call GetNextArray
call getchar
mov byte ptr di,al
mov si,0
next1:
cmp di,S.len
jl loop4
jmp rettt
loop4:
cmp si,T.len
jl loop5
jmp rettt
loop5:
cmp si,-1
jnz loop6
loop6:
cmp S.str[di],T.str[si]
jnz loop7
jmp loop8
loop7:
mov si,next[si]
jmp next1
loop8:
inc di
inc si
jmp next1
rettt:
cmp si,T.len
jge ret1
mov dx,offset fail
mov ah,09h
int 21h
ret1:
mov dx,offset success
mov ah,09h
int 21h

pop si
pop di
pop bx
pop ax
pop cx
pop dx
ret
KMP endp

GetNextArray proc far
push si
push di
push bx
push ax
push cx
push dx
mov di,0
mov si,-1
mov next[di],-1
next:
cmp di,T.len-1
jge rett
cmp si,-1
jnz loop2
loop2:
cmp T.str[di],T.str[si]
jnz loop3
jmp loop1
loop3:
mov si,next[si]
jmp next
loop1:
inc di
inc si
mov next[di],si
jmp next
rett:
pop si
pop di
pop bx
pop ax
pop cx
pop dx
ret
GetNextArray endp

getchar proc
mov ah,02h
int 21h
sub 30h
ret
getchar endp
code ends
end start

按照第二个改了下，可能存在很多错误，可以编译通过，接下来的任务就是你自己去改了，输入字符串你自己弄吧