2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(15)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理匯總

　　19、kmp算法

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

　　intKMP(const char *Text,const char *Pattern) //const 表示函數(shù)內(nèi)部不會(huì)改變這個(gè)參數(shù)的值

　　{

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

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

　　int len=0;

　　const char *c=Pattern;

　　while(*c++!='\0')//移動(dòng)指針比移動(dòng)下標(biāo)快。

　　{

　　++len;//字符串長(zhǎng)度。

　　}

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

　　get_nextval(Pattern, next); //求Pattern的next函數(shù)值

　　int i=0, j=0;

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

　　{

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

　　{

　　++i; // 繼續(xù)比較后繼字符

　　++j;

　　}

　　else

　　{

　　j=next[j]; // 模式串向右移動(dòng)

　　}

　　}//while

　　delete []next;

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

　　}

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

　　{

　　//求模式串T的next函數(shù)值并存入數(shù)組 next。

　　int j = 0,;

　　int k = next[0] = -1;

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

　　{

　　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

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)