2015年初级软考辅导:串匹配算法(C&assembly)
发布时间：2010/3/13 14:38:29 来源：城市学习网 编辑：MOON
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
{
if(j==-1p==p[j])
{
i++; j++;
next=j;
}
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
{
if(s==p[j])
{ i++; j++; }
else
{
j=next[j];
if(j==-1) { i++; j++; }
}
}
if(i
return (i-j);
else
return -1;
#else
_asm
{
push edi
push esi
push ebx
push ecx
push edx
mov edi， dword ptr[s]
mov esi， dword ptr[p]
mov edx， dword ptr[next]
xor ebx， ebx
xor ecx， ecx
_While_:
cmp ebx， dword ptr[ls]
jge _EndWhile_ ;大于等于转移
cmp ecx， dword ptr[lp]
jge _EndWhile_ ;大于等于转移
_If_:
mov ah， byte ptr[edi+ebx]
mov al， byte ptr[esi+ecx]
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
}
