KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n)，KMP匹配算法。可以证明它的时间复杂度为O(m+n)。
怎么求串的模式值 next[n]
定义 ：
（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符不等（或者相等但T[k]==T[j]）（1≤k如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] （1≤k T[0]T[1]T[2]。。。T[k-1] == T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且
T[j]!=T[k]（1≤k(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
举例 ：
01）求T=“abcac”的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据 (4) 因（3）有1<=k next[2]=0 根据 (4) 因（3）有1<=k next[3]= -1 根据 (2)
next[4]=1 根据 (3) T[0]=T[3] 且 T[1]!=T[4]
即
下标 0 1 2 3 4
T a b c a c
next -1 0 0 -1 1
若T=“abcab”将是这样：
下标 0 1 2 3 4
T a b c a b
next -1 0 0 -1 0
为什么T[0]==T[3],还会有next[4]=0呢, 因为T[1]==T[4], 根据 (3)” 且T[j] != T[k]”被划入（4）。
02）来个复杂点的，求T=”ababcaabc” 的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据(4)
next[2]=-1 根据 (2)
next[3]=0 根据 (3) 虽T[0]=T[2] 但T[1]=T[3] 被划入（4）
next[4]=2 根据 (3) T[0]T[1]=T[2]T[3] 且T[2] !=T[4]
next[5]=-1 根据 (2)
next[6]=1 根据 (3) T[0]=T[5] 且T[1]!=T[6]
next[7]=0 根据 (3) 虽T[0]=T[6] 但T[1]=T[7] 被划入（4）
next[8]=2 根据 (3) T[0]T[1]=T[6]T[7] 且T[2] !=T[8]
即
下标 0 1 2 3 4 5 6 7 8
T a b a b c a a b c
next -1 0 -1 0 2 -1 1 0 2
只要理解了next[3]=0，而不是=1，next[6]=1，而不是= -1，next[8]=2，而不是= 0，其他的好象都容易理解。
03) 来个特殊的，求 T=”abCabCad” 的模式函数的值。
下标 0 1 2 3 4 5 6 7
T a b C a b C a d
next -1 0 0 -1 0 0 -1 4
next[5]= 0 根据 (3) 虽T[0]T[1]=T[3]T[4],但T[2]==T[5]
next[6]= -1 根据 (2) 虽前面有abC=abC,但T[3]==T[6]
next[7]=4 根据 (3) 前面有abCa=abCa,且 T[4]!=T[7]
若T[4]==T[7]，即T=” adCadCad”,那么将是这样：next[7]=0, 而不是= 4,因为T[4]==T[7].
下标 0 1 2 3 4 5 6 7
T a d C a d C a d
next -1 0 0 -1 0 0 -1 0
求匹配串的模式函数值：
|
void get_nextval(const char* pattern, int next[])
{
int j=0, k=-1;
next[0] = -1;
while(pattern[j] != '\0')
{
if(k!=-1 && pattern[k]!=pattern[j])
{
k = next[k];
}
k++;
j++;
if(pattern[k] == pattern[j])
{
next[j] = next[k];
}
else
{
next[j] = k;
}
}
}
|
完整测试KMP的程序如下：
|
#include <iostream>
using namespace std;
void get_nextval(const char* pattern, int next[])
{
int j=0, k=-1;
next[0] = -1;
while(pattern[j] != '\0')
{
if(k!=-1 && pattern[k]!=pattern[j])
{
k = next[k];
}
k++;
j++;
if(pattern[k] == pattern[j])
{
next[j] = next[k];
}
else
{
next[j] = k;
}
}
}
//KMP算法，匹配成功返回匹配位置(首字符索引)，失败返回-1
int KMP(const char *text, const char *pattern)
{
int len = strlen(pattern);
int *next = new int[len+1];
int index=0, i=0, j=0;
if(!text || !pattern || '\0'==text[0] || '\0'==pattern[0])
{
cerr<<"空指针或空串，KMP执行失败！"<<endl;
exit(0);
}
get_nextval(pattern, next); //求匹配串的next数组值
while('\0'!=text[i] && '\0'!=pattern[j])
{
if(text[i] == pattern[j])
{
i++; //继续比较后续字符
j++; //
}
else
{
index += j-next[j];
if(next[j] != -1)
j = next[j]; //模式串向右移动
else //若next[j]==1，表示pattern[j]与text[i]已经间接匹配过了，不相等。
{
j = 0;
i++;
}
}
}
delete[] next;
if('\0' == pattern[j])
return index; //匹配成功
else
return -1;
}
void main()
{
char * text = "bababCabCadcaabcaababcbaaaabaaacababcaabc";
char * pattern = "adcaab";
cout<<KMP(text, pattern)<<endl;
}
|
阅读(828) | 评论(0) | 转发(0) |
