KMP数组的求法及应用

应用场景

KMP数组解决的是字符串匹配问题：给定字符串p和t，问p在t中第一次出现的位置是哪里？
如果使用暴力匹配，设p的长度为m， t的长度为n，时间复杂度为O(m, n）
而KMP算法提供了一种新的思路：如果p的第0~j - 1位与t的第i ~ i + j - 1位已经匹配了，那么我们能不能利用这个信息呢？答案是可以。
于是给出了next数组的定义：next[j] = k，表示p的第0~k位与j - 1 - k ~ j - 1 位完全相等。那么我们发现p的第j位失配后，只需要将j = next[j]，便能保证前j - 1位匹配。
这样，时间复杂度为O(m + n)

void find_next(string str, vector<int> &next)
{
    int i = 0;
    int k = -1;
    int len = str.length();
    next = vector<int> (len, 0);
    next[0] = -1;

    while (i < len - 1)
    {
        while (k >= 0 && str[i] != str[k])
        {
            k = next[k];
        }
        i++;
        k++;
        next[i] = k;
    }
}

是根据有限状态机的思路来写的
重点是：next数组怎么使用

int i = 0, k = -1;
    int len = s.length();
    vector<int> next(len + 1, 0);
    next[0] = -1;
    while (i < len)
    {
        while (k >= 0 && s[i] != s[k])
        {
            k = next[k];
        }
        i++;
        k++;
        next[i] = k;
    }
    int loop_len = len - next.back();

除了字符串匹配以外，KMP数组最常见的应用是：求一个字符串的循环。在求循环的时候，需要多求一位，使用len - next[len]作为循环节长度。

int kmp(string p, string t)
{
    vector<int> next;
    int i = 0, j = 0;
    find_next(p, next);
    int tLen = t.length(), pLen = p.length();
    while (i < tLen && j < pLen)
    {
        if (j == -1 || t[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j >= pLen)
    {
        return i - pLen;
    }
    return -1;
}

这个函数求的则是字符串匹配