KMP.rar_patternmatch资源-CSDN文库

共1个文件

txt：1个

版权申诉

160 浏览量 2022-09-21 05:46:48 上传评论收藏 856B RAR 举报

《KMP算法——高效模式匹配的C++实现》在计算机科学中，字符串搜索或模式匹配是一项基础且重要的任务，特别是在文本处理、数据挖掘和编译器设计等领域。KMP（Knuth-Morris-Pratt）算法就是一种解决这个问题的有效方法，它避免了不必要的回溯，提高了搜索效率。本文将深入探讨KMP算法的原理及其C++实现。 KMP算法由D.E. Knuth、V.R. Morris和J. Pratt于1970年提出，其核心思想是利用已知的前缀和后缀信息来避免无效的比较。在传统的朴素模式匹配算法中，当主串中的一个字符与模式串不匹配时，需要从头开始重新匹配。而KMP算法通过构建部分匹配表，可以知道在遇到不匹配时，模式串应如何移动，从而避免了不必要的回溯。部分匹配表（也称为失配表）是KMP算法的关键。对于模式串P，部分匹配表LPS（Longest Proper Prefix which is also Suffix）记录了每一个位置i之前形成的最长公共前后缀的长度。例如，模式串"ABABCAB"的部分匹配表为[0, 0, 1, 2, 0, 3, 0]。在实际匹配过程中，如果当前字符不匹配，我们可以根据部分匹配表快速确定下一个要比较的位置，而无需回溯。 C++实现KMP算法通常包括以下步骤： 1. 构建部分匹配表LPS。 2. 主串S与模式串P进行逐字符比较，依据LPS表进行状态转移。以下是C++实现KMP算法的基本框架： ```cpp #include <iostream> #include <vector> // 构建部分匹配表LPS std::vector<int> computeLPS(const std::string &pattern) { int length = pattern.size(); std::vector<int> lps(length, 0); int index = 0; for (int i = 1; i < length; ++i) { while (index > 0 && pattern[i] != pattern[index]) { index = lps[index - 1]; } if (pattern[i] == pattern[index]) { ++index; } lps[i] = index; } return lps; } // KMP算法 void KMP(const std::string &text, const std::string &pattern) { std::vector<int> lps = computeLPS(pattern); int index = 0, textIndex = 0; while (textIndex < text.size()) { if (pattern[index] == text[textIndex]) { ++index; ++textIndex; } else if (index > 0) { index = lps[index - 1]; } else { ++textIndex; } if (index == pattern.size()) { std::cout << "Pattern found at position " << textIndex - index << std::endl; index = lps[index - 1]; } } } int main() { std::string text = "ABABCABXYZABABC"; std::string pattern = "ABABC"; KMP(text, pattern); return 0; } ``` 在这个示例中，`computeLPS`函数用于计算部分匹配表，`KMP`函数则执行实际的模式匹配。当找到模式串时，程序会输出其在主串中的起始位置。 KMP算法的时间复杂度为O(m + n)，其中m是模式串长度，n是主串长度，这比朴素的O(mn)方法有了显著的优化。它的优点在于避免了无效的回溯，尤其是在模式串中存在重复子串时，性能优势更加明显。总结来说，KMP算法是一种高效的模式匹配方法，通过构建部分匹配表，可以有效地减少不必要的比较，提高搜索效率。在C++中实现KMP算法，可以帮助我们快速地在主串中查找特定模式串，广泛应用于各种字符串处理场景。理解并掌握KMP算法，对于提升编程能力，尤其是处理字符串问题的能力，具有重要意义。

资源推荐

资源详情

资源评论

收起资源包目录

KMP.rar （1个子文件）

KMP.txt 3KB

#include <iostream> #include <vector> #include <functional> #include <algorithm> using namespace std; template<typename FType, typename SType> struct equal_cmp { bool operator ()(const FType& _F, const SType& _S)const {return _F == _S;} }; template<typename RandAccessConcept, typename EqualCmp> inline void CalFailFunction( const RandAccessConcept& in, int len, vector<int>& ff, EqualCmp cmp ) { ff.clear(); ff.reserve(len); ff.push_back(-1); for (int curr = 1, k = -1; curr < len; ++curr) { for (;k >= 0 && !cmp(in[k+1], in[curr]); k = ff[k]); if (cmp(in[k+1], in[curr])) ++k; ff.push_back(k); } } template<typename FRandAccessConcept, typename SRandAccessConcept, typename EqualCmp> inline int KMPSearchFirst( const FRandAccessConcept& d, int dlength, const SRandAccessConcept& p, int plength, EqualCmp cmp, int start = 0 ) { vector<int> ff; CalFailFunction(p, plength, ff, cmp); for (int i = start, j = -1; i < dlength; ++i) { while (j >= 0 && !cmp(d[i], p[j+1])) j = ff[j]; if (cmp(d[i], p[j+1])) ++j; if (j == plength - 1) return i - plength + 1; } return -1; } template<typename FRandAccessConcept, typename SRandAccessConcept, typename EqualCmp> inline int KMPSearchALL( const FRandAccessConcept& d, int dlength, const SRandAccessConcept& p, int plength, vector<int>& result, EqualCmp cmp ) { vector<int> ff; CalFailFunction(p, plength, ff, cmp); result.clear(); AN>for (int i = 0, j = -1; i < dlength; ++i) { while (j >= 0 && !cmp(d[i], p[j+1])) j = ff[j]; if (cmp(d[i], p[j+1])) ++j; if (j == plength - 1) { result.push_back(i - plength + 1); j = ff[j]; } } return result.size(); } int main() { int d[] = {1,2,3,1,2,3,1,2}; char p[] = "\1\2\3\1\2"; vector<int> result; int found = KMPSearchALL(d, 8, p, 5, result, equal_cmp<int, char>()); for (int i = 0; i < found; ++i) cout << result[i] << " "; cout << endl; return 0; }

评论收藏

内容反馈

版权申诉