KMP算法的详细解释及实现

这是我自己学习算法时有关KMP的学习笔记，代码注释的十分的详细，分享给大家，希望对大家有所帮助 在介绍KMP算法之前，

先来介绍一下朴素模式匹配算法：

朴素模式匹配算法：

假设要从主串S=”goodgoole”中找到T=”google”这个字串的位置，我们需要一下的步骤：

1，主串S的第一位开始，S与T的前三个字母都能成功匹配，但是S的第四个字母是d，而T的第四位是g，所以主串S的第一位匹配失败

2，然后从主串的第二位开始，会发现主串的第二位字母与T的第一位字母不同，所以匹配失败，然后再从主串的第三位开始，

3，经过这样的依次尝试后，之到主串的第五位开始，S与T的6个字母完全匹配成功

该朴素模式匹配算法的代码实现是：

该算法的功能是返回字串T在主串S中第pos个字符之后的位置，若不存在，则函数返回值为0，前提是T非空且1<pos<StrLength(S)

int Index(char* S,char* T,int pos)//index是索引的意思

{

int i=pos-1;//i用于主串S中当前位置的下标,S[0]是主串T的第一个字符

int j=0;//j用于子串T中当前位置下标值，即T[0]是字串T的第一个字符

while(i<strlen(S)&&j<strlen(T))

{

if(S[i]==T[j])//如果主串S当前的字母与子串的字母相等则继续

{

++i;

++j;

}

else

{

i=i-j+1;//eg:如果第一次匹配时，不相等则使i=i-j+2=i+1;即向下走一个字母，以i=0为例，刚开始从主串第一个位置开始，如果S[i]==T[j]一直满足，则i和j同步变化，即i=j;一旦有不相等的字母时，i=i-j+1,实际就是i=1；然后再从主串的第二个字母开始

j=0;//重新匹配时，j又回到T的子串的首位

}

}

if(j==strlen(T))//此时已完成匹配

return i-strlen(T);//返回

else

return 0;

}

KMP模式匹配算法

KMP算法中把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度；

next数组值得推导：

T="abcdex";(前后缀一个字符相等，k值是2，两个字符相等，k值是3，n个k值相等k值就是就是n+1)

1,当j=1时，next[1]=0;

2,当j=2时，j由1到j-1只有字符"a",next[2]=1;

3,当j=3时，j由1到j-1就只有字符串"ab"，显然"a"与"b"不相等，所以next[3]=1;

4,同理得：T串的next[j]为011111;

T="ababaaaba";

1,当j=1时，next[1]=0;

2,当j=2时，next[2]=1;

3,当j=3时，next[3]=1;

4,当j=4时，next[4]=2;//j由1到j-1的串是"aba",前缀字符"a"与后缀字符"a"相等，next[4]=2;

5,当j=5时，next[5]=3;//串是"abab",前缀是"ab",后缀是"ab",有两个相同的字符，所以为3

6,当j=6时，next[6]=4;//串是"ababa",前缀是"aba"，后缀是"aba",有三个相同的字符，所以为4

7,当j=7时，next[7]=2;//串是"ababaa",前缀字符是"a"与后缀字符"a"相等，有两个相同的字符，所以为2

8,当j=8时，next[8]=2;//串是"ababaaa",前缀字符是"a"与后缀字符"a"相等，有两个相同的字符，所以为2

9,当j=9时，next[9]=3;//串是"ababaaab",前缀字符是"ab",后缀字符也为"ab",有两个相同的字符，所以为3

10,当j=10时，next[10]=4;//串是"ababaaaba",前缀字符是"aba",后缀字符也为"aba",有三个相同的字符，所以为4

KMP模式匹配算法实现

1，通过计算返回子串T的next数组

void get_next(char* T,int *next)

{

　 int i,j;

　　 　i=1;

　j=0;

　　　next[1]=0;

　　 while(i<=strlen(T))

　　{

　　if(j==0||T[i-1]==T[j-1])

{

++i;

++j;

next[i]=j;

}//以T="abcdex"为例：该循环的执行顺序:第一步,j=0,执行,（i=2,j=1,next[2]=1）第二步，不符合循环条件，j=next[1]=0,j又变为0为了再次进入循环，(i=3,j=1,next[3]=1)依次往下循环

else

j=next[j];

}

}

//这段代码的目的就是为了计算出当前要匹配的串T的next数组

int Index_KMP(char* S,char* T,int pos)

{

int i=pos;

int j=1;

int next[255];

get_next(T,next);

while(i<=strlen(S)&&j<=strlen(T))

{

if(j==0||S[i-1]==T[j-1])

{

++i;

++j;

}

else

j=next[j];//起到回溯的作用

}

if(j>strlen(T))

return (i-strlen(T)-1);

else

return 0;

}

附加一个实例：

#include<iostream>

using namespace std;

void get_next(char* T,int *next)

{

int i,j;

　　 i=1; j=0;

　　next[1]=0;

　while(i<=strlen(T))

{

if(j==0||T[i-1]==T[j-1])

{　　　　　　　　　　　　　

　　　　　　　 ++i;

++j;

next[i]=j;

}//以T="abcdex"为例：该循环的执行顺序:第一步,j=0,执行,（i=2,j=1,next[2]=1）第二步，不符合循环条件，j=next[1]=0,j又变为0为了再次进入循环，(i=3,j=1,next[3]=1)依次往下循环

else

j=next[j];

}

}//这段代码的目的就是为了计算出当前要匹配的串T的next数组

int Index_KMP(char* S,char* T,int pos)

{

int i=pos;

int j=1;

int next[255];

get_next(T,next);

while(i<=strlen(S)&&j<=strlen(T))

{

if(j==0||S[i-1]==T[j-1])

{

++i;

++j;

}

else

j=next[j];//起到回溯的作用

}

if(j>strlen(T))

return (i-strlen(T)-1);

else

return 0;

}

int main()

{

　　char* T="bc";

　　 char* S="babaacbababcbababcbcbc";

　　 int pos=1;

　　int next[255];

　　get_next(T,next);

　　for(int j=1;j<=2;j++)

　　 cout<<"j="<<j<<":"<<"next"<<"["<<j<<"]"<<next[j]<<endl;

　　cout<<"子串T在主串S第"<<pos<<"个字符之后的第"<<Index_KMP(S,T,pos)<<"个位置"<<endl;

　　 return 0;

}