kmp算法模板及理解

kmp算法是复杂度为O(n+m)的字符串匹配算法;

首先kmp算法的核心是在模式串中获得next数组,这个数组表示模式串的子串的前缀和后缀相同的最长长度;

这样在匹配的过程中如果指到不匹配的位置,模式串用next数组进行跳转到符合的位置,而目标串不需要再往回匹配,为什么是最长的相同的前缀后后缀呢？

因为只有这样才能一边避免可能漏掉的位置,一边尽量不重复已经匹配的位置;

getNext的函数：

void getNext()

{

    int k = -,j = ,len = strlen(str);

    next[] = -;

    while(j < len)

    {

        if(k == -||str[j] == str[k])

        {

            j++;

            k++;

            next[j] = k;//相等的话就往后继续;

        }

        else k = next[k];//不等的话就相当于kmp一样,把模式串的这个子串用已经求出来的next跳转;

    }

}

kmp算法代码：

int kmp()

{

    int posP = ,posT = ;

    int lenP = strlen(strP),lenT = strlen(strT);

    while(posP < lenP&&posT < lenT)

    {

        if(posP == -||strP[posP] == strT[posT])

        {

            posP++;

            posT++;

        }

        else posP = next[posP];

        if(posP == lenP)return posT-lenP;//匹配成功返回匹配成功的位置;

    }

    return -;//匹配失败哦;

}

巴特西

kmp算法模板及理解

最新文章

热门文章