KMP 算法是字符串匹配领域的经典算法，相比暴力匹配的O(n∗m)时间复杂度，KMP 通过预处理模式串生成 next 数组，将时间复杂度优化到O(n+m)（n 为主串长度，m 为模式串长度）。本文会从核心思想出发，结合我手写的 C++ 代码，用最易懂的方式讲解 KMP 算法，重点聚焦 “公共前后缀” 法求 next 数组的实现思路。
1. KMP算法核心思想
暴力匹配的问题在于：一旦字符不匹配，主串指针会回退到起始位置的下一位，模式串指针回退到 0，大量重复比较导致效率低下。
KMP 的核心优化是：利用模式串的 “最长相等公共前后缀” 信息，当字符不匹配时，主串指针不回退，仅调整模式串指针到合适位置，避免重复比较。
举个简单例子：模式串abaabc匹配到某位置失败时，不需要从头匹配，而是根据已匹配部分的公共前后缀，直接跳到最优位置继续匹配。
2. 关键概念：最长相等公共前后缀
要理解 next 数组，首先要懂 “最长相等公共前后缀”：
- 前缀：字符串中不包含最后一个字符的所有以第一个字符开头的子串（如aba的前缀：a、ab）
- 后缀：字符串中不包含第一个字符的所有以最后一个字符结尾的子串（如aba的后缀：a、ba）
- 最长相等公共前后缀：前缀和后缀中长度最长且内容相等的子串长度（如aba的最长相等公共前后缀长度为 1，对应子串a）
3. 完整 C++ 实现代码
#include<iostream>
using namespace std;int getPub(string str);//获取公共前后缀
void getNext(string str,int arr[]);//获取next数组
int KMP_me(string s,string t,int next[]);//KMP
void show(int arr[],int n);//展示next数组int main()
{string s="abaacaabcabaabc"; //主串string t="abaabc"; //模板串int next[t.length()];getNext(t,next);cout << "模式串\"" << t << "\"的next数组：";show(next,t.length());int pos = KMP_me(s,t,next); //通过KMP获取位置if(pos == -1)printf("未从<%s>中找到<%s>\n",s,t);elseprintf("匹配成功！\n%s\n%*s%s\n",s.c_str(),pos,"",t.c_str());return 0;
}int getPub(string str) //获取公共前后缀
{//原则上要求字符串长度至少为2int pub = 0; //默认为0int length = str.length(); //字符串长度for(int i=1;i<length;i++)//判断从长度1到length-1的前缀与后缀是否相等if(str.substr(0,i)==str.substr(length-i,i))pub = i;return pub;
}void getNext(string str,int arr[]) //获取next数组
{//原则上要求字符串长度至少为1int length = str.length();arr[0] = -1; if(length == 1) return;arr[1] = 0; if(length == 2) return;for(int i=2;i<length;i++)arr[i] = getPub(str.substr(0,i));
}int KMP_me(string s,string t,int next[]) //KMP
{int i=0,j=0;int sL = s.length();int tL = t.length();while(i<sL&&j<tL){if(j==-1||s[i]==t[j]){i++;j++;}elsej=next[j];}if(j==tL)return i-tL;elsereturn -1;
}void show(int arr[],int n) //展示next数组
{for(int i=0;i<n;i++)printf("<%d> ",arr[i]);puts(""); //实际只是用来换行
}
4. 代码核心模块解析
(1)getPub 函数（求最长公共前后缀）
- 功能：输入一个字符串，返回其最长相等公共前后缀的长度；
- 实现逻辑：遍历 1 到字符串长度 - 1 的所有可能长度，逐一比较前缀（substr(0, i)）和后缀（substr(length-i, i)）是否相等，记录最大的相等长度；
- 示例：输入"aba"，会依次比较i=1（前缀a、后缀a，相等）、i=2（前缀ab、后缀ba，不相等），最终返回 1。
(2)getNext 函数（生成 next 数组）
next 数组的长度等于模式串长度，每个位置next[i]表示：模式串前i个字符的最长相等公共前后缀长度，核心规则：
- next[0] = -1：算法约定，用于处理模式串第一个字符就不匹配的情况；
- next[1] = 0：长度为 2 的字符串，无有效公共前后缀；
- i≥2时：调用getPub函数，计算模式串前i个字符的最长公共前后缀长度，赋值给next[i]；
- 示例：模式串abaabc的 next 数组为：<-1> <0> <1> <0> <1> <2>。
(3)KMP_me 函数（核心匹配）
- 双指针遍历：i遍历主串，j遍历模式串；
- 匹配成功：i++、j++，继续比较下一个字符；
- 匹配失败：j = next[j]（模式串指针回退到最优位置），i不回退；
- 终止条件：要么主串遍历完（未匹配），要么模式串遍历完（匹配成功）；
- 返回值：匹配成功返回起始位置（i-tL），失败返回 - 1。
(4)运行结果示例
模式串"abaabc"的next数组：<-1> <0> <1> <0> <1> <2>
匹配成功！
abaacaabcabaabcabaabc