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
