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

会计考友 发表于 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;
//计算模式串
next=-1;
int i=0; int j=-1;
while（i

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

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

}
else
j=next;
}
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