kmp改进算法
⑴ 模式p='abcaababc '的KMP算法和KMP,并改进算法的匹配过程!
求子串next[j]值的算法:
void GetNext(String T, int next[])
{ int j = 1, k = 0;
next[1] = 0;
while(j < len(T)){
if( k == 0 || T[j]==T[k])
{j++; k++; next[j]=k; }
else k = next[k];
}
}
KMP 算法的自然语言描述
设s为主串,t为模式串,设i为主串s当前比较字符的下标,j为模式串t当前比较字符的下标,令i和j的初值为pos和1。当si = tj时,i和j分别增1再继续比较;否则 i不变,j改变为next[j]值(即模式串右滑)后再继续比较。依次类推,直到出现下列两种情况之一:
一是 j退回到某个j=next[j]值时有si = tj ,则 i和j分别增1后再继续比较;
二是j退回到j=0时,令主串和子串的下标各增1,随后比较si和t1 。这样的循环过程一直进行到变量大于等于s的长度或变量j大于等于t的长度为止。
int KMPIndex(String S, int start,String T, int next[ ])
{
int i = start, j=1;
while ( i <= S[0] && j< T[0]) {
//不失配则继续比较后续字符
if (j == 0 || S [i] = = T[j] ) {i++; j++ }
//特点:S的i指针不回溯,而且从T的k位置开始匹配
else j=next[j];
}
if (j >= T[0]) return ( i-T(0) );
else return -1;
}
⑵ kmp算法的优化
KMP算法是可以被进一步优化的。
我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”,经过KMP算法,应当得到“特征向量”如下表所示: 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 但是,如果此时发现p(i) == p(k),那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格: 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 优化的next[i] -1 0 0 0 -1 1 0 0 3 0 (1)next[0]= -1 意义:任何串的第一个字符的模式值规定为-1。
(2)next[j]= -1 意义:模式串T中下标为j的字符,如果与首字符
相同,且j的前面的1—k个字符与开头的1—k
个字符不等(或者相等但T[k]==T[j])(1≤k<j)。
如:T=”abCabCad” 则 next[6]=-1,因T[3]=T[6]
(3)next[j]=k 意义:模式串T中下标为j的字符,如果j的前面k个
字符与开头的k个字符相等,且T[j] != T[k] (1≤k<j)。
即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<j);
(4) next[j]=0 意义:除(1)(2)(3)的其他情况。
补充一个next[]生成代码: voidgetNext(constchar*pattern,intnext[]){next[0]=-1;intk=-1,j=0;while(pattern[j]!='