19、kmp算法
voidget_nextval(const char *T, int next[]);
intKMP(const char *Text,const char *Pattern) //const 表示函数内部不会改变这个参数的值
{
if( !Text||!Pattern|| Pattern[0]=='/0' ||Text[0]=='/0' )
return -1;//空指针或空串,返回-1
int len=0;
const char *c=Pattern;
while(*c++!='/0')//移动指针比移动下标快。
{
++len;//字符串长度。
}
int *next = new int[len+1];
get_nextval(Pattern, next); //求Pattern的next函数值
int i=0, j=0;
while(Text[i]!='/0' &&Pattern[j]!='/0' )
{
if(j = -1 || Text[i]== Pattern[j])
{
++i; // 继续比较后继字符
++j;
}
else
{
j=next[j]; // 模式串向右移动
}
}//while
delete []next;
return Pattern[j]=='/0' ? (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*/] != '/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
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。