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<lp-1)
　　{
　　if(j==-1||p==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<ls&&j<lp)
　　{
　　if(s==p[j])
　　{ i++; j++; }
　　else
　　{
　　j=next[j];
　　if(j==-1) { i++; j++; }
　　}
　　}
　　if(i<ls)
　　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
　　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
　　}

3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.net/exam/