KMP

KMP

一、算法引入

当我们想要在主串中查找子串的位置时，我们可以采用暴力求解，比较主串指针（主串上的箭头）与子串指针（子串上的箭头）的字母，直到子串全部比对完成，

当我们遇到不一样的时候，将主串指针移动到主串指针开始时的位置的后一位置。子串指针移动到子串第一个位置，继续比对两指针的字母

但是这样时间复杂度太高，有什么方法可以使得主串的指针不后移，一直向前，这样就可以大大减少比对次数，提高效率。这就需要使用KMP算法了

二、算法演示

首先仍然是一一比对

此时我们遇到了第一个与子串不同的字母，由于我们已经匹配过前面的字母了，那这时候是不是可以将子串指针移动到这个位置，主串指针不移动呢？

子串前两个字母 AB 与主串指针现在指向的位置的前两个字母是匹配的，所以我们完全可以跳过AB的匹配，继续后面的匹配就行了，直到匹配完成

有一种情况是我们子串指针后的字符数已经比主串指针后的字母数多了，那主串肯定就不存在子串了。

但是我们是怎么知道子串的指针该移动到哪里呢？这就需要用到next[]数组了

三、next[]的作用

先不需要管next是怎么得来的，这里我们定义，next[i]表示i+1字符匹配失败时，移动子串指针后可以忽略前next[i]个字母的匹配

比如：

我们发现C的前一个字母B对应的next值是2，所以移动子串指针后可以忽略前2个字母的匹配，即我们把子串指针移动到第三个位置

然后继续匹配剩余字母即可，这样我们也就达成了不需要回退主串指针，实现字符串的匹配。

注意：

不同的人对于next[]的定义是不一样的，但是道理是一样的。

然后我们再来说说next[]的含义，next[i]表示的是前i及i之前的子串的 相同前后缀的长度的最大值（这个子串的前后缀的长度是小于子串的）

对于第一个字母，长度只有1，那么前后缀长度只能为0，那自然next值为0

对于AB，长度最大为1，但是A 显然与B不相同，所以next值也是0

对于ABA 前缀AB 与后缀BA不相同，只有前缀A 与后缀 A相同，所以next值为1

对于ABAB 前缀AB 与后缀AB相同，所以next值为2

同理C对应的则为0

这样我们就得到了next[]数组。

其实我们从我们得到next[]的过程中，我们就可以明白为什么下面那个数值就是可以忽略的个数，因为，他们是相同的子串，而且在当前子串指针前的所有字符我们都是已经确定了是匹配的了，所以我们现在就可以把前面的那一小段子串给忽略掉了。

四、next[]的计算

我们可以使用for循环暴力求解，但这样就违背我们最初选择的初衷了，这样并没有完全做到优化，我们采用一种递推的方式来求解next[]

举个例子，假设我们已经知道目前的前缀长度为2，

接下来分两种情况，如果下一个字母还相同，很明显前缀长度加一，

如果下一个字母不相同，

既然ABA 与 B 结合不能构成更长的前后缀，那我们考虑ABA中有没有短一点的子串能够与B构成次长的前后缀的？也就是BA与B可不可以，A与B可不可以，如果最后都不可以，那么B的next值为0。

这一步我们也不需要暴力求解，因为根据之前的计算，我们可以确定，前面肯定有一段也是ABA与后面的ABA 相同的，那么我们完全可以在前面的那段ABA中找这个“短一点的子串”。

而我们已经求过了ABA这段的最长的前后缀（就是上方我们要求的“短一点的子串”）长度是1，

那么我们现在我们又回到了最初的步骤，比较下一个字母是相同还是不同。这里我们发现是相同的，所以前缀长度加一。

假如我们这里遇到的是不同的情况，比如这种：

此时我们就需要去A这段里去找“短一点的子串”，查表可以知道是0：

此时是0了，然后回到最初步骤，比较下一个字母是不是相同的，这里的下一个字母其实就是第一个字母，因为前缀长度为0了。

很显然又是不同的，但是都已经是跟第一个字母不同了，就不可以继续往下递推了，此时D的next值就是0

我们用prefixLen表示当前前缀长度（每张图最上边那个值），我们能够发现一个规律，当我们的下一个字母不同时，prefixLen = next[prefixLen - 1] 这里-1是因为next[]下标从0开始，所以不同情况不同对待。

我们来推理一下这个规律。

根据上面说的，我们要从前面的那段ABC中去寻找，然后我们从下标为2的位置读出了ABC的next值，我们此时的prefixLen是3，也就是我们去的那段串的长度为3，因为我们next从0开始，所以位置是2，也就是长度减一，即prefixLen = next[prefixLen - 1] 这个公式代码中会用到。

五、代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> next_; // next数组

void initNext(string str)
{
    next_.push_back(0); // 第一个必然为0
    int prefixLen = 0;  // 当前共同前后缀长度
    int i = 1;          // 计算next[i]

    while (i < str.length())
    {
        if (str[prefixLen] == str[i])
        { // 与下一个字母相同
            prefixLen++;
            next_.push_back(prefixLen);
            i++;
        }
        else
        { // 与下一个字母不同
            if (prefixLen == 0)
            {
                // 这里prefixLen为0时没有判断str[prefixLen]是否等于str[i]，因为if判断了，所以在执行这条语句是，总会判断
                next_.push_back(0);
                i++;
            }
            else
            {
                prefixLen = next_[prefixLen - 1];
            }
        }
    }
}

int KMPSearch(string s1, string s2)
{              // s1为主串，s2为子串
    int i = 0; // 主串指针
    int j = 0; // 子串指针

    while (i < s1.length())
    {
        if (s2.length() - j > s1.length() - i) // 子串剩余字母数超过了主串，那肯定不会匹配了
        {
            return -1;
        }
        if (s1[i] == s2[j])
        { // 相同则指针都后移
            i++;
            j++;
        }
        else if (j > 0) // j如果不大于0，子串不需要移动
        {               // 不相等，根据next忽略起那几个字母
            j = next_[j - 1];
        }
        else
        {
            i += 1;
        }

        if (j == s2.length())
        {                 // 匹配成功
            return i - j; // 得出位置
        }
    }

    return -1;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    initNext(s2); // 求next数组
    cout << KMPSearch(s1, s2);
}

洛谷KMP模板题

AC代码：

#include <iostream>
#include <vector>
using namespace std;

vector<int> next_; // next数组
vector<int> ans;

void initNext(string str)
{
    next_.push_back(0); // 第一个必然为0
    int prefixLen = 0;  // 当前共同前后缀长度
    int i = 1;          // 计算next[i]

    while (i < str.length())
    {
        if (str[prefixLen] == str[i])
        { // 与下一个字母相同
            prefixLen++;
            next_.push_back(prefixLen);
            i++;
        }
        else
        { // 与下一个字母不同
            if (prefixLen == 0)
            {
                // 这里prefixLen为0时没有判断str[prefixLen]是否等于str[i]，因为if判断了，所以在执行这条语句是，总会判断
                next_.push_back(0);
                i++;
            }
            else
            {
                prefixLen = next_[prefixLen - 1];
            }
        }
    }
}

void KMPSearch(string s1, string s2)
{              // s1为主串，s2为子串
    int i = 0; // 主串指针
    int j = 0; // 子串指针

    while (i < s1.length())
    {
        if (s2.length() - j > s1.length() - i) // 子串剩余字母数超过了主串，那肯定不会匹配了
        {
            return;
        }
        if (s1[i] == s2[j])
        { // 相同则指针都后移
            i++;
            j++;
        }
        else if (j > 0) // j如果不大于0，子串不需要移动
        {               // 不相等，根据next忽略起那几个字母
            j = next_[j - 1];
        }
        else
        {
            i += 1;
        }

        if (j == s2.length())
        {                         // 匹配成功
            ans.push_back(i - j); // 得出位置
        }
    }

    return;
}

int main()
{
    // freopen("E:\\C++Code\\in.txt", "r", stdin);
    // freopen("E:\\C++Code\\out.txt", "w", stdout);

    string s1, s2;
    cin >> s1 >> s2;
    initNext(s2); // 求next数组
    KMPSearch(s1, s2);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] + 1 << '\n';
    }
    for (int i = 0; i < next_.size(); i++)
    {
        if (i == 0)
            cout << next_[i];
        else
            cout << " " << next_[i];
    }
}