KMP算法概述KMP算法Knuth-Morris-Pratt算法是一种高效的字符串匹配算法用于在主串中查找模式串的出现位置。其核心思想是利用部分匹配表Partial Match TablePMT或失败函数Failure Function来避免不必要的回溯从而将时间复杂度优化至O(nm)其中n为主串长度m为模式串长度。不重叠匹配计数问题不重叠匹配计数要求统计模式串在主串中的所有出现次数且这些出现的位置不能重叠。例如主串为ABABABA模式串为ABA不重叠匹配结果为2位置0和4而重叠匹配结果为3位置0、2、4。KMP算法实现不重叠匹配计数构建部分匹配表PMT部分匹配表记录了模式串前缀和后缀的最长公共长度。对于模式串PPMT[i]表示P[0..i]的最长公共前后缀长度。vectorint computePMT(const string pattern) { int m pattern.size(); vectorint pmt(m, 0); int len 0; for (int i 1; i m; ) { if (pattern[i] pattern[len]) { len; pmt[i] len; i; } else { if (len ! 0) { len pmt[len - 1]; } else { pmt[i] 0; i; } } } return pmt; }KMP搜索实现不重叠匹配计数在KMP搜索过程中每当找到一个匹配时跳过整个模式串的长度以避免重叠。int kmpNonOverlappingCount(const string text, const string pattern) { int n text.size(); int m pattern.size(); if (m 0 || n m) return 0; vectorint pmt computePMT(pattern); int count 0; int i 0; // text的索引 int j 0; // pattern的索引 while (i n) { if (text[i] pattern[j]) { i; j; if (j m) { count; j 0; // 重置pattern索引避免重叠 } } else { if (j ! 0) { j pmt[j - 1]; } else { i; } } } return count; }示例与测试以下是一个完整的C示例包含测试用例#include iostream #include vector #include string using namespace std; vectorint computePMT(const string pattern) { int m pattern.size(); vectorint pmt(m, 0); int len 0; for (int i 1; i m; ) { if (pattern[i] pattern[len]) { len; pmt[i] len; i; } else { if (len ! 0) { len pmt[len - 1]; } else { pmt[i] 0; i; } } } return pmt; } int kmpNonOverlappingCount(const string text, const string pattern) { int n text.size(); int m pattern.size(); if (m 0 || n m) return 0; vectorint pmt computePMT(pattern); int count 0; int i 0; int j 0; while (i n) { if (text[i] pattern[j]) { i; j; if (j m) { count; j 0; } } else { if (j ! 0) { j pmt[j - 1]; } else { i; } } } return count; } int main() { string text ABABABA; string pattern ABA; cout Non-overlapping count: kmpNonOverlappingCount(text, pattern) endl; text AAAAA; pattern AA; cout Non-overlapping count: kmpNonOverlappingCount(text, pattern) endl; text ABCABCABC; pattern ABC; cout Non-overlapping count: kmpNonOverlappingCount(text, pattern) endl; return 0; }时间复杂度分析PMT构建O(m)其中m为模式串长度。KMP搜索O(n)其中n为主串长度。总时间复杂度O(n m)。应用场景KMP算法的不重叠匹配计数适用于以下场景文本编辑器中查找非重叠关键词。生物信息学中DNA序列的非重叠模式匹配。数据压缩中重复模式的检测。优化与扩展多模式匹配结合AC自动机扩展为多模式串匹配。并行化利用多线程加速大规模文本的匹配。空间优化使用滚动数组减少PMT的空间占用。总结KMP算法通过部分匹配表避免了不必要的回溯高效解决了字符串匹配问题。通过调整匹配后的索引重置逻辑可以轻松实现不重叠匹配计数。其线性时间复杂度和简洁的实现使其成为字符串匹配的首选算法之一。核心内容聚焦于HDU 2087剪花布条这一编程题目的求解其核心算法是通过KMP算法在不重叠计算的前提下统计一个模式串小饰条在主串花布条中出现的最大次数 。特简单第一步、问题定义与算法核心问题要求从给定的主串s花布条中尽可能多地剪出与模式串t小饰条完全匹配且互不重叠的片段。这本质上是一个字符串匹配计数问题但关键在于匹配成功的子串不能共享字符。KMP算法通过其前缀函数next数组或文中的ne数组实现了高效的匹配时间复杂度为 O(nm)。文章明确指出实现不重叠与重叠计数的唯一区别在于匹配成功后的指针重置逻辑当j lent即完全匹配一次时若需不重叠计数则j0模式串指针从头开始若需重叠计数则jne[j]利用已匹配部分继续尝试匹配 。第二步、提供的两种解决方案文章提供了两种实现路径基于std::string::find的内置函数方法该方法利用C标准库的s1.find(s2, p)函数进行迭代查找。每次成功找到模式串后计数器cnt加1并将查找起始位置p向后移动模式串的长度(p s2.length())。这一操作逻辑直接保证了匹配的片段不会重叠。基于KMP算法的经典实现这是文章的技术重点。代码清晰分为两部分getNext函数构建模式串T的nenext数组用于在匹配失败时高效跳转。KMP函数执行主匹配逻辑。其关键代码块如下当一次完整匹配达成时 (if(jlent))计数器cnt增加随后执行j0;将模式串指针重置确保了后续匹配不会与本次已匹配的区间产生重叠 。第三步、输入输出与样例解析文章给出了明确的输入输出格式和样例。输入以#作为结束标志。通过分析样例aaaaaa和aa输出结果为3直观验证了不重叠匹配的规则主串可被划分为三个独立的aa而非五个重叠计算的结果。非常重要第四步、关联对比文章通过引用另一道题目HDU 1686Oulipo进行对比强调了通过修改KMP匹配成功后j的赋值语句 (j0与jne[j])即可灵活切换不重叠与重叠两种计数模式体现了KMP算法在此类问题上的通用性与微调便利性 。详见hnjzsyjyj的文章比我的更加详细非常推荐求赞QWQ参考来源HDU 2087剪花布条 ← KMP算法不重叠计算