计算机软考程序员辅导：串匹配算法

会计考友 · 发表于 2012-8-2 08:51:15

Knuth-Morris-Pratt（缩写KMP）串匹配算法是一个基本的串操作算法，在各种含有串操作的程序中广泛使用。 KMP匹配的最大优点在于——主串无需回溯，故可以用于数据流的匹配，如可顺序读入文件的过程中实现匹配，提示同时它也是各种匹配算法中速度最快的。
此处给出了算法的C代码。另外，还写了一段汇编优化的参考代码，虽无太大用处但仍可作为汇编优化的参考。

#define _USEASM_
//求模式串的Next数组
// p: 模式串
// lp: 模式串长度
inline int * getNext（const char * p, int lp=-1）
{
if（lp==-1）
lp=（int）strlen（p）;
//前一个模式串的Next数组
static int * next=NULL;
//如果有数据先释放内存
if（next） delete[] next;
//为Next数组分配存储空间
next=new int[lp];
//计算模式串
next[0]=-1;
int i=0; int j=-1;
while（i

会计考友 · 发表于 2012-8-2 08:51:16

}
else
j=next[j];
}
return next;
}
//Knuth-Morris-Pratt模式匹配算法
// s：源串
// p：模式串
int instr（const char * s, const char * p）
{
int ls=（int）strlen（s）;
int lp=（int）strlen（p）;
int * next=getNext（p，lp）;
#ifndef _USEASM_
int i=0; int j=0;
while（i

会计考友 · 发表于 2012-8-2 08:51:17

if（i

会计考友 · 发表于 2012-8-2 08:51:18

cmp ah,al
jnz _Else_
;_If_
inc ebx
inc ecx
jmp _EndIf_
_Else_:
shl ecx, 2
mov ecx, dword ptr[edx+ecx]
cmp ecx, -1
jnz _EndIf_
inc ebx
inc ecx
_EndIf_:
jmp _While_
_EndWhile_:
_If2_:
cmp ebx, dword ptr[ls]
jge _Else2_
mov eax, ebx
sub eax, ecx
jmp _EndIf2_
_Else2_:
mov eax, -1
_EndIf2_:
pop edx
pop ecx
pop ebx
pop esi
pop edi
}
#endif
}

		自动登录	找回密码
密码			立即注册

[程序员] 计算机软考程序员辅导：串匹配算法