//
//字符串模式匹配：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

评论