一、前言介绍今天进入字符串专项学习经典的KMP 算法解决高效字符串匹配问题。二、暴力匹配的问题暴力思路主串s长度 n模式串p长度 m逐位比对失配时主串指针回退、模式串指针归零。 时间复杂度 \(O(n\times m)\)长字符串场景效率极低。KMP 核心优化失配后指针不盲目回退利用已有匹配信息跳过无效比对时间复杂度降至 \(O(nm)\)。三、KMP 核心概念前缀字符串从首字符开始不包含自身的子串后缀字符串从末尾结束不包含自身的子串最长相等前后缀同一个子串既是前缀也是后缀取长度最大值next 数组记录模式串每个位置的最长相等前后缀长度是 KMP 的核心四、next 数组求解重点next[i]表示模式串p[0~i]子串的最长相等前后缀长度。 利用递推方式求解无需重复计算。求 next 数组代码#include iostream #include string #include vector using namespace std; // 求解next数组 void getNext(string p, vectorint next) { int m p.size(); next.resize(m, 0); int j 0; // 前缀末尾指针 // i 从1开始next[0]固定为0 for(int i 1; i m; i) { // 不相等回退到next[j-1] while(j 0 p[i] ! p[j]) j next[j - 1]; if(p[i] p[j]) j; next[i] j; } }五、KMP 匹配主逻辑规则主串指针i全程不回退只向后移动模式串指针j失配时根据next数组回退j next[j-1]j走完模式串长度说明匹配成功完整匹配代码// KMP 查找返回模式串在主串中首次出现的下标未找到返回-1 int kmp(string s, string p, vectorint next) { int n s.size(), m p.size(); int j 0; for(int i 0; i n; i) { while(j 0 s[i] ! p[j]) j next[j - 1]; if(s[i] p[j]) j; // 匹配完成 if(j m) return i - m 1; } return -1; }六、整合完整版模板直接刷题使用#include iostream #include string #include vector using namespace std; void getNext(string p, vectorint next) { int m p.size(); next.resize(m, 0); int j 0; for(int i 1; i m; i) { while(j 0 p[i] ! p[j]) j next[j - 1]; if(p[i] p[j]) j; next[i] j; } } int kmpSearch(string s, string p) { vectorint next; getNext(p, next); int n s.size(), m p.size(); int j 0; for(int i 0; i n; i) { while(j 0 s[i] ! p[j]) j next[j - 1]; if(s[i] p[j]) j; if(j m) return i - m 1; } return -1; } int main() { string str ababcabcabx; string pat abcab; int pos kmpSearch(str, pat); cout 匹配起始下标 pos endl; return 0; }七、多位置匹配改造查找所有出现位置如果需要找出模式串所有匹配位置匹配成功后让j next[j-1]继续查找void kmpFindAll(string s, string p) { vectorint next; getNext(p, next); int n s.size(), m p.size(); int j 0; for(int i 0; i n; i) { while(j 0 s[i] ! p[j]) j next[j - 1]; if(s[i] p[j]) j; if(j m) { cout 找到匹配起始下标 i - m 1 endl; j next[j - 1]; // 继续向后查找 } } }八、核心要点总结KMP 优势线性时间匹配长字符串场景碾压暴力算法核心载体next数组存储最长相等前后缀长度两大步骤先求 next 数组再执行字符串匹配指针规则主串指针不回退模式串依靠 next 数组回退应用场景文本查找、关键词过滤、字符串重复子串判断九、常见易错点求解 next 数组时i从 1 开始next[0]恒为 0失配回退条件必须加上j0防止下标越界多位置匹配时匹配成功后不能直接置j0要用next[j-1]十、课后练习手动计算简单模式串的 next 数组加深理解运行完整 KMP 代码测试不同主串、模式串改写代码实现找出所有匹配位置