kmp算法报告

 算法思想

KMP算法是基于BF算法的低效率进行改进的，因此在介绍KMP算法之前先让我们来了解BF算法。

BF的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的\"匹配\"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。

KMP算法先根据已经部分匹配的信息，将匹配的指针跳过不必匹配的位置。 在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

 算法步骤

Step1:分别指示主串、模式串比较位置的指针i,j 初始化。

Step2:重复下列操作，直至S中所剩字符个数小于T的长度或T中所有字符均比较完。

2.1 如果si=tj, i和j 分别增一；否则； 2.2 j=next[j]

2.3 如果 j=0,则将i 和j 分别加一。

Step3：如果T中所有字符均比较完，则反回匹配的起始下标；否则，返回-1.

 算法实现

#include #include using namespace std;

void getNext(const char* pattern,int next[]) {

next[0]= -1; int k=-1,j=0;

while(pattern[j] != '\\0') {

if(k!= -1 && pattern[k]!= pattern[j] ) k=next[k]; ++j;++k;

if(pattern[k]== pattern[j]) next[j]=next[k]; else

next[j]=k; }

//这里是我加的显示部分 // for(int i=0;i// cout<//cout<int KMP(const char *Text,const char* Pattern)

//const 表示函数内部不会改变这个参数的值。 {

if(!Text||!Pattern||Pattern[0]=='\\0'||Text[0]=='\\0' )

//return -1; //空指针或空串，返回

-1。

int len=0;

const char * c=Pattern;

while(*c++!='\\0')//移动指针比移动下标快。 {

++len; //字符串长度。 }

int *next=new int[len+1];

getNext(Pattern,next);

//求Pattern的next函数值

int index=0,i=0,j=0;

while(Text[i]!='\\0'&& Pattern[j]!='\\0' ) {

if(Text[i]== Pattern[j]) {

++i; // 继续比较后继字符 ++j; } else {

index += j-next[j]; if(next[j]!=-1)

j=next[j]; // 模式串向右移动 else {

j=0; ++i; } } }//while

delete []next;

if(Pattern[j]=='\\0') return index; // 匹配成功 else

return -1; }

int main() //abCabCad {

int n[50];

char* text=\"bababCabCadCadCaddabcbaaaabaaacababcaabc\"; char*pattern=\"adCadCad\"; getNext(pattern,n);

cout< 算法结果

表示“adCadCad”在主串里从第九个字符开始有一样的字符串（在主串中字符从0开始标记）。

 算法改良

KMP算法是可以被进一步优化的。

我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i p(i) next[i] 0 a -1 1 b 0 2 c 0 3 d 0 4 a 0 5 a 1 6 b 1 7 c 2 8 a 3 9 b 1 但是，如果此时发现p(i) == p(k），那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格： 下标i p(i) 0 a 1 b 2 c 3 d 4 a 5 a 6 b 7 c 8 a 9 b next[i] 优化的next[i] -1 -1 0 0 0 0 0 0 0 -1 1 1 1 0 2 0 3 3 1 0 （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。 （2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符 相同，且j的前面的1—k个字符与开头的1—k 个字符不等（或者相等但T[k]==T[j]）（1≤k