数据结构例程——串的模式匹配（KMP算法）

本文针对数据结构基础系列网络课程(4)：串中第5课时串的模式匹配（KMP算法）。

问题：串的模式匹配

KMP算法：

#include <stdio.h>
#include "sqString.h"
void GetNext(SqString t,int next[])  /*由模式串t求出next值*/
{
    int j,k;
    j=0;
    k=-1;
    next[0]=-1;
    while (j<t.length-1)
    {
        if (k==-1 || t.data[j]==t.data[k])  /*k为-1或比较的字符相等时*/
        {
            j++;
            k++;
            next[j]=k;
        }
        else  
            k=next[k];
    }
}
int KMPIndex(SqString s,SqString t)  /*KMP算法*/
{
    int next[MaxSize],i=0,j=0;
    GetNext(t,next);
    while (i<s.length && j<t.length)
    {
        if (j==-1 || s.data[i]==t.data[j])
        {
            i++;
            j++;            /*i,j各增1*/
        }
        else j=next[j];         /*i不变,j后退*/
    }
    if (j>=t.length)
        return(i-t.length);         /*返回匹配模式串的首字符下标*/
    else
        return(-1);             /*返回不匹配标志*/
}
int main()
{
    SqString s,t;
    StrAssign(s,"ababcabcacbab");
    StrAssign(t,"abcac");
    printf("s:");
    DispStr(s);
    printf("t:");
    DispStr(t);
    printf("位置:%d\n",KMPIndex(s,t));
    return 0;
}

修正后的KMP算法

#include <stdio.h>
#include "sqString.h"
void GetNextval(SqString t,int nextval[])  //由模式串t求出nextval值
{
    int j=0,k=-1;
    nextval[0]=-1;
    while (j<t.length)
    {
        if (k==-1 || t.data[j]==t.data[k])
        {
            j++;
            k++;
            if (t.data[j]!=t.data[k])
                nextval[j]=k;
            else
                nextval[j]=nextval[k];
        }
        else  k=nextval[k];
    }

}
int KMPIndex1(SqString s,SqString t)    //修正的KMP算法
{
    int nextval[MaxSize],i=0,j=0;
    GetNextval(t,nextval);
    while (i<s.length && j<t.length)
    {
        if (j==-1 || s.data[i]==t.data[j])
        {
            i++;
            j++;
        }
        else
            j=nextval[j];
    }
    if (j>=t.length)
        return(i-t.length);
    else
        return(-1);
}
int main()
{
    SqString s,t;
    StrAssign(s,"ababcabcacbab");
    StrAssign(t,"abcac");
    printf("s:");
    DispStr(s);
    printf("t:");
    DispStr(t);
    printf("位置:%d\n",KMPIndex1(s,t));
    return 0;
}