KMP算法

KMP算法

简单的模式匹配算法

int Index(SString S,SString T)
{
    int i=1,j=1;
    while(i<=S[o]&&j<=T[0])
    {
        if(S[i]=T[j])
        {++i;++j;}
        else
        {i=i-j+2;j=1;}
    }
    if(j>T[0])
    return i-T[0];
    else return 0;
}
复制代码

-时间复杂度为O（m*n）

• 定义next【j】数组

• 算法分析

1. next[1]=0,next[2]=1;

• 求next【】函数算法如下：

void get_next(char T[],int next[]) {
    i=1;
    next[1]=0;
    j=0;
    while(i<=T[0])
    {
        if(j==0||T[i]==T[j])
        {
        ++i;++j;next[i]=j;
        }
        else
        j=next[j]
    }
}

复制代码

改进的next算法

• kmp算法

int index_KMP(SString S,SString T,int pos)
{
    i=pos,j=1;
    while(i<S.length&&j<T.length)
    {
        if(j==0||S.ch[i]==T.ch[j])
        {
            i++;j++;
        }
        else
        j=next[j];
        
    }
    if(j>T.length)
    return i-T.length;
    else
    return 0;
}
复制代码