在日常使用的搜索引擎中，系统是如何快速从海量长文本里精确找到我们所需的模式串的呢？暴力匹配算法虽然能解决问题，但其时间复杂度高达 O(m×n)，当文本规模较大时效率难以接受。有没有更高效的算法呢？这就需要引入 KMP 算法。

文章目录

• 一、字符串匹配问题引入
• • 1. 什么是字符串匹配？
  • 2. 暴力匹配算法
  • 3.暴力算法问题
• 二、KMP算法核心思想
• • <1>KMP核心就是可以避免回退主串
  • <2> 什么是next数组？
  • <3> next数组图解
• 三、KMP匹配过程详解（重点）
• 四、KMP代码实现
• • 1.next数组的构建
  • 2.KMP匹配代码
• 五、为什么可以根据next数组而进行跳跃呢？

一、字符串匹配问题引入

1. 什么是字符串匹配？

介绍：

• 主串（Text）：被查找的字符串
• 模式串（Pattern）：要寻找的字符串

例如：
主串：
ABABDABACDABABCABAB

模式串：
ABABCABAB

目标：
找出模式串第一次出现的位置。、

2. 暴力匹配算法

介绍普通做法：主串逐个位置开始尝试匹配 ，失败后主串向后移动一位，重新比较

举例：

主串：
A B A B C A B A B

模式：
A B A B D
        ↑
       失败

然后重新从：

      A B A B C
        ^

开始。

3.暴力算法问题

分析：
假设：

• 主串长度 n
• 模式串长度 m

最坏情况：O(n*m)
例如：

AAAAAAAAAB

AAAAAB

大量重复字符导致重复比较

二、KMP算法核心思想

<1>KMP核心就是可以避免回退主串

普通算法：

主串指针 i
模式串指针 j

失败：
i 回退
j 回到0

KMP算法:

主串 i 不动

只调整模式串 j

重点： 已经匹配的信息不浪费，例如主串 S：A B A B C A B A B ，模式串 P：A B A B D，第一次匹配失败时，已经成功匹配的：A B A B 这 4 个字符是确定正确的， 暴力会把 P 直接挪到最开头，S 指针回退 ；而KMP利用已经匹配上的ABAB的最长相等前后缀（下面会讲到）：

• 前缀：A B
• 后缀：A B
  所以模式串不用回到 0，直接回退到下标 2 的位置，主串 S 的指针原地不动，不用回头。

<2> 什么是next数组？

next数组作为KMP算法最核心的部分，记录当前字符串前缀和后缀最长相同长度。

例如：

模式串：

abab

分析：

前缀：

a
ab
aba

后缀：

b
ab
bab

最长相同：ab

长度：2

所以：next[3]=2

<3> next数组图解

下标	字符	最长公共前后缀
0	a	0
1	b	0
2	a	1
3	b	2

模式：

a b a b
0 0 1 2

三、KMP匹配过程详解（重点）

拿一个例子

主串：
a b a b a b c a b c a


模式：
a b a b c a 

匹配：

a b a b c
0 1 2 3 4

a b a b已经匹配，但c != a
此时查看next[3] = 2，说明a b已经匹配，所以j跳到 2 （最后讲解了为什么可以进行跳跃)

a b a b c a
0 1 2 3 4 5
    ^
    j=2

而主串

a b a b a b c a
        ^
      从这里开始

然后继续比较

主串位置4:
a

模式位置2:
a

成功！ 然后

i++
j++

继续：

主串位置5:
b

模式位置3:
b

继续：

主串位置6:
c

模式位置4:
c

成功！ 继续：

主串位置7 = a

模式位置5 = a

匹配完成

四、KMP代码实现

1.next数组的构建

• pattern：模式串（你想寻找的字符串）
• i 代表当前正在计算next的位置。
• j 代表当前最长公共前后缀长度。

void GetNext(const char* pattern, vector<int>& next)
{
    int len = strlen(pattern);

    next.resize(len);//next数组大小与模式串一致

    if(len == 0)
        return;


    // 第0个字符没有前后缀
    next[0] = 0;

    int j = 0;
    
    for(int i = 1; i < len; i++)
    {
        // 当前字符匹配失败
        while(j > 0 && pattern[i] != pattern[j])
        {
            // 寻找更短的公共前后缀
            j = next[j - 1];
        }


        // 匹配成功
        if(pattern[i] == pattern[j])
        {
            j++;
        }


        // 保存当前位置的最长前后缀长度
        next[i] = j;
    }
}

2.KMP匹配代码

• i表示主串位置
• j表示模式串位置
• text文本串

int KMP(const char* text, const char* pattern)
{
    int m = strlen(text);//文本串长度
    int n = strlen(pattern);//模式串长度


    if(n == 0)
        return 0;


    vector<int> next;

    GetNext(pattern, next);


    int i = 0;
    int j = 0;



    while(i < m)
    {
        // 当前字符匹配
        if(text[i] == pattern[j])
        {
            i++;
            j++;
            
            // 模式串全部匹配完成
            if(j == n)
            {
                return i - j;
            }
        }
        else
        {
            // 匹配失败，但是之前有匹配信息
            if(j > 0)
            {
                j = next[j - 1];
            }
            else
            {
                // 没有任何匹配信息
                i++;
            }
        }
    }
    
    return -1;
}

五、为什么可以根据next数组而进行跳跃呢？

在构建 next 数组时，我们先将模式串中的每个字符看作一个节点。现在需要计算位置j的最长公共前后缀长度。

假设在计算过程中，已经知道位置 8 的最长公共前后缀长度为 4，即图中两块蓝色区域完全相同。

此时需要继续判断位置 9 是否能够扩展这个长度，因此会比较:

pattern[j] 和pattern[len]对应的字符。

如果二者相等，那么位置 9 的最长公共前后缀长度自然变为：len + 1

但如果二者不相等，则说明长度为 4 的公共前后缀无法继续扩展。

这时我们并不需要重新从头开始寻找，因为长度为 4 的公共前后缀内部本身可能还存在更短的公共前后缀。

例如，已知长度为 4 的公共前后缀中还存在一个长度为 2 的公共前后缀（即图中的 A1 与 A2 相等）。

又因为蓝色区域相等，所以A1 = A4

因此，当长度为 4 的方案失效后，我们可以直接退回到长度为 2 的方案，并在此基础上继续比较下一个字符，而无需重新从头匹配。

如果仍然失配，则继续寻找长度更短的公共前后缀，直到找到可扩展的位置或退回到 0。、

正如代码中：

j = next[j - 1];