KMP算法讲解与代码
本帖最后由 andalousie 于 2014-4-5 21:44 编辑因为自己感觉字符串这块儿特别薄弱，就学习了KMP算法。参考了小甲鱼的视频以及csdn和一些资料。发表此文，仅表对小甲鱼的佩服和感激。
大家都很明白，KMP的重点在于理解next数组的含义，抄个代码本不难，对吧。所以我的ppt里面主要给出了next数组的生成过程，而搜索匹配子串其实很简单。下面是截图
接着给出代码实现。ppt回复可见。
#include <iostream>
#include <string>
class KMP
{
std::string pat;
int M;
int * next;
public:
// create Knuth-Morris-Pratt NFA from pattern
KMP(const std::string& pattern)
: pat(pattern), M(pattern.length())
{
next = new int;
int i, j = -1;
for (i = 0; i < M; i++)
{
if ( i == 0 ) next = -1;
else if ( pat != pat ) next = j;
else next = next;
while ( j >= 0 && pat != pat )
j = next;
j++;
}
for (i = 0; i < M; i++)
std::cout << "next[" << i << "] = " << next << std::endl;
}
~KMP() { delete [] next; }
// return offset of first occurrence of text in pattern (or N if no match)
// simulate the NFA to find match
int search(const std::string& text)
{
int N = text.length();
int i, j;
for (i = 0, j = 0; i < N && j < M; i++) {
while (j >= 0 && text != pat)
j = next;
j++;
}
if (j == M) return i - M;
return N;
}
};
int main()
{
std::string pattern = "ababaca";
KMP kmp(pattern);
std::string text = "abababaca";
int offset = kmp.search(text);
std::cout << text << std::endl;
for (int i = 0; i < offset; i++)
std::cout << " ";
std::cout << pattern << std::endl;
}**** Hidden Message *****
盗用了下小甲鱼课件的背景哈~ 我也在看这个，过来看看 先看看在说 感谢分享，收藏了 看看学习学习 :sad 互惠吧 受教了 :sad 互惠吧 受教了 谢谢楼主分享 两包烟的钱，把不了妹买不了田，不如拿来支持小甲鱼推出更多原创教学视频！ 支持下…… 感谢lz分享。~ 感谢楼主分享，顶贴支持～ 这东西不错呀，非常感谢楼主分享。。。！ 向楼主学习学习 好啊啊{:1_1:} 这个很好的 支持 感谢楼主无私分享！！！！！！！ 支持小甲鱼！！支持小甲鱼！！ 支持楼主