KMP的next[]数组

KMP是众多字符串问题的基础

理解next数组尤为重要

next又称前缀数组

是 它所处位置的前一个位置的元素 与 该链 链首开始 几个元素相匹配(即相同)

举个实例来说明：

next对应的是该位置的前一个元素， 即next[i]对应a[i-1]

因为-1头指针的存在 next均对应前一个 很重要

next可以理解为指针，而它指向的位置 就是他的数值对应下标的前一个

即 比如next[7]指向a[ next[7] - 1 ], 也就是a[2]  next[13]指向a[ next[13] - 1 ], 也就是a[5];

结合上一条， 也就是a[6]对应a[2]                           a[12]对应a[5]

这样对应的含义是： a[x]与a[y]对应，那么  从链首至a[y]的元素 均能与 a[x]及其之前 相同长度的元素匹配

举个例子 a[12]对应a[5]， 也就是说 a[0]到a[5]这六个元素 能与 a[12]往前(包括a[12])共六个元素匹配  就是 a[0]到a[5] 与 a[7]到a[12] 相同

这样对应了起来有什么用呢？

这就为查找失败 往前找节约了时间。

比如， 我们在第14 这个位置查找失败了， 那么我们只需要回到next[14]这个位置也就是a[7], 看a[7]是否匹配, 若不匹配 再往前回next[7]也就是a[3]的位置

直至查找成功或者回到0

为什么呢？

因为next 数组的含义 简单的说 就是 前面有多少匹配

所以当不匹配了， 只需找到上一个匹配到哪里就可以了。

实现:

next数组的实现也是用的这个原理

void getnext(int len)
{
    int i=0, j=-1;
    next[0]=-1;
    while(i<len)
    {
        if(j==-1 || b[i]==b[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

int kmp(int la,int lb)
{
    int i=0, j=0;
    while(i<la && j<lb)
    {
        if(j==-1 || a[i]==b[j])
        {
            i++;
            j++;
        }
        else
            j=next[j];
    }
    if(j>=lb)
        return i-lb+1;
    else
        return -1;
}