KMP算法C++代码

KMP算法的思想一般数据结构书都有讲，没讲的话google一下，有很多文章解释了其思想。晚上写了写这个代码，虽然不难，但还是费了番功夫调试，出现的主要问题有：无符号整型数据与整型数据比较大小（让我越来越讨厌无符号数！），还有一个问题就是KMP算法本身与求next数组的算法很类似，但是有些微妙的区别，也让调试了几次。

 

int* GetNextVal(const char *s, int &len)
{
    len = strlen(s);
    int *next = new int[len];
    int i = 0;
    int j = -1;
    next[0] = -1;
    while(i<len-1)//注意这里跟KMP函数里面的不同
    {
        if(j==-1 || s[i]==s[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    return next;
}

int KMP(const char *s, const char *t)
{
    int slen,tlen;
    int i,j;
    int *next = GetNextVal(t, tlen);
    slen = strlen(s);
    i = 0;
    j = 0;
    while(i<slen && j<tlen)
    {
        if(j==-1 || s[i]==t[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }

    delete[] next;

    if(j==tlen)
        return i - tlen;
    return -1;
}

int main(int argc, char *argv[])
{
    char s[128],t[128];
    while(cin>>s>>t)
    {
        int pos1 = KMP(s,t);
        int pos2 = strstr(s,t) - s;
        cout<<pos1<<":"<<pos2<<endl;
    }
    return 0;
}