KMP算法——用于字符串匹配。优点是在匹配的过程中不用回退主指针，子指针会根据子串中最长相等前后缀来进行回退，能够大大降低时间复杂度。
  这里有几个定义需要说明：

  • 前缀：不包含尾字符的所有子串
  • 后缀：不包含首字符的所有子串

  举例：T = aabaaf

子串 说明 最长相等前后缀的长度
$t_1=\mathrm{a}$ 无前缀也无后缀 $\pi \left( 0 \right) =0$
$t_1=\mathrm{aa}$ 前缀为$\small{\mathrm{a}}$后缀也为$\small{\mathrm{a}}$ $\pi \left( 1 \right) =1$
$t_1=\mathrm{aab}$ 前缀一定无$\small{\mathrm{b}}$后缀一定有$\small{\mathrm{b}}$ $\pi \left( 2 \right) =0$
$t_1=\mathrm{aaba}$ 最大相等前后缀为$\small{\mathrm{a}}$ $\pi \left( 3 \right) =1$
$t_1=\mathrm{aabaa}$ 最大相等前后缀为$\small{\mathrm{aa}}$ $\pi \left( 4 \right) =2$
$t_1=\mathrm{aabaaf}$ 无最大相等前后缀 $\pi \left( 5 \right) =0$
$\mathrm{j}$ 0 1 2 3 4 5
$T$ a a b a a f
$\pi(T)$ 0 1 0 1 2 0

  一般也把$\small{\pi(T)}$叫做前缀表，前缀表中保存的元素就是子指针回退的位置。编程实现中，也叫 next 数组。具体计算如下：

1
2
3
4
5
6
7
8
9
10
11
void NextTable(vector<int>& next, string s)
{
    next[0] = 0;
    int j = 0;
    for(int i = 1; i < s.size(); i++)
    {
        while(j > 0 && s[j] != s[i]) j = next[j - 1];
        if(s[i] == s[j]) j++;
        next[i] = j;
    }
}

力扣 28

  找出字符串中第一个匹配项的下标
  这个题目就是一道经典的匹配问题，暴力解法同时遍历 haystack 和 needle，时间复杂度为$\small{O(M*N)}$，空间复杂度为$\small{O(1)}$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int strStr(string haystack, string needle)
{
    int i = -1;// 如果匹配失败返回 -1
    for(int j = 0; j<haystack.size();)
    {
        int k = 0;
        while(k < needle.size())
        {
            // 如果匹配到相同字符，j++，k++
            if(haystack[j++] == needle[k])
                k++;
            else
                // 如果没有直接退出循环
                break;
        }
        // 如果上一步循环得到的 k 等于 needle 大小，说明 needle 得到完全匹配
        if(k == needle.size()) 
        {
            // 直接作差（此时 j 和 k 没有起始下标偏差，直接做差）
            i = j - k;
            // 跳出遍历
            break;
        }
        // 如果没有匹配到，则回退 j 到本次匹配 第一个匹配相同的位置 的下一个
        j = j - k;
    }
    return i;
}

  如果用 KMP 算法，时间复杂度为$\small{O(M+N)}$，空间复杂度为$\small{O(M)}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int strStr(string haystack, string needle)
{
    // 创建 next 表
    vector<int> next(needle.size(), 0);
    int j = 0;
    for(int i = 1; i < needle.size(); i++)
    {
        while(j > 0 && needle[i] != needle[j]) j = next[j - 1];
        if(needle[i] == needle[j]) j++;
        next[i] = j;
    }
    for(int i = 0, j = 0; i < haystack.size(); i++)
    {
        while(j > 0 && haystack[i] != needle[j]) j = next[j - 1];
        if(haystack[i] == needle[j]) j++;
        if(j == needle.size()) return i - j + 1;
    }
    return -1;
}

  可以发现 KMP 算法无论是创建前缀表还是应用前缀表，代码具有高度相似性。