2011年软考程序员考试复习笔试知识点整理(15)

 　19、kmp算法

　　voidget_nextval(const char *T, int next[]);

　　intKMP(const char *Text,const char *Pattern) //const 表示函数内部不会改变这个参数的值

　　{

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

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

　　int len=0;

　　const char *c=Pattern;

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

　　{

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

　　}

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

　　get_nextval(Pattern, next); //求Pattern的next函数值

　　int i=0, j=0;

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

　　{

　　if(j = -1 || Text[i]== Pattern[j])

　　{

　　++i; // 继续比较后继字符

　　++j;

　　}

　　else

　　{

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

　　}

　　}//while

　　delete []next;

　　return Pattern[j]=='' ? (len - i) :-1; //返回

　　}

　　voidget_nextval(const char *T, int next[])

　　{

　　//求模式串T的next函数值并存入数组 next。

　　int j = 0,;

　　int k = next[0] = -1;

　　while ( T[j/*+1*/] != '' )

　　{

　　if (k == -1 || T[j] == T[k])

　　{

　　++j;

　　++k;

　　if (T[j] != T[k])

　　next[j] = k;

　　else

　　next[j] = next[k];

　　}// if

　　else

　　k = next[k];

　　}// while

　　}//get_nextval