////字符串模式匹配：KMP算法////06.05.07 vc6.0调试通过//ZYQ//#include <iostream.h>#include <string>int* get_next(char *T);void main(){    char* s="hhhsauhduwdh";    char* t="hdu";    int i=0;    int j=0;    int S=strlen(s);    int T=strlen(t);    int *next=get_next(t);    while(i<S&&j<T)    {//判定条件i<S&&j<T说明：字符串数组下标从0开始，到字符串长度减1结束        if(j==0||s[i]==t[j])        {i++;j++;}//继续向后比较字符        else            j=next[j];//模式串向后移动    }    if(j>=T)        cout<<i-T+1<<endl;//匹配成功    else        cout<<"0"<<endl;//匹配失败}//KMP算法克服了主串中i指针的回朔问题//求next值的算法//06.05.07 get_next函数调试时仍有问题。编译时通过，运行时出错。//int* get_next(char *T){//返回指向next数组首地址的指针    int i=1;    int next[100];    next[1]=0;    int j=0;    while(i<strlen(T))    {        if(j==0||T[i]==T[j])        {i++;j++;next[i]=j;}        else j=next[j];    }//while    return next;}//get_next

评论