KMP算法实验
1．编程计算模式串（子串）的next值。
2．利用KMP算法在主串中找到模式串的位置。
参考代码：
---------
int getNexlVal( char * s, int j)//求字符串S的j的模式值
{
if( j == 1) return 0;//j=1，next[j]=0
int max = 0;//其他情况，next[j]=max+1=1
for( int l = 1; l < j-1 ; l ++ )//从K前面第l个数开始找
{
for( int k = 1; k <=l; k ++)//k代表从字符串开始的l的前面的数遍历
{
if( s[k] != s[j-l+k-1] ) break;//字符串从头开始的第k个值与第j个数前的第l个值不相等，跳出
}
if(k == (l+1))//j前有l个数和从头开始的l个数相同，第l+1=k个数不同
{
if(max <l) max = l;//max=l
}
//模式串s中下标为j的字符，如果j的前面k个
//字符与开头的k个字符相等，且T[j] != T[k]
}
return max+1;//next[j]=max+1=l+1=k
}
void getNext( char * s, int * val)
{
printf("VAL%s:",s);
for( int i = 1; i< strlen(s); i ++ )
{
val[i] = getNexlVal( s, i);
printf("%d ",val[i]);
}
printf("\n");
return;
}
int KMP( char * r, char *s , int * v)
{
int i = 1;
int j = 1;
while( i<strlen(r) && j<strlen(s))
{
if( j==0 || r[i] == s[j] ){ i++; j++; }//继续比较后续字符
else j = v[j];//模式串向右移动
}
if( j == strlen(s)) { printf("FOUND @ %d \n", i-j+1); return i-j;}//匹配成功
else return 0;
}
int main(int argc, char* argv[])
{
char s[10];
char r[100];
int next2[10];
printf("子串：\n");
scanf("%s",s);
printf("主串：\n");
scanf("%s",r);
getNext(s,next2);
KMP( r,s,next2);
return 0;
}