马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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[M];
int i, j = -1;
for (i = 0; i < M; i++)
{
if ( i == 0 ) next[i] = -1;
else if ( pat[i] != pat[j] ) next[i] = j;
else next[i] = next[j];
while ( j >= 0 && pat[i] != pat[j] )
j = next[j];
j++;
}
for (i = 0; i < M; i++)
std::cout << "next[" << i << "] = " << next[i] << 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[i] != pat[j])
j = next[j];
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;
}
盗用了下小甲鱼课件的背景哈~ | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2014-4-5 21:37:45
置顶卡
千斤顶
显身卡
发表于 2014-4-19 17:09:31