链接：http://blog.csdn.net/joylnwang/article/details/6778316
KMP算法是一种很经典的字符串匹配算法，链接中的讲解已经是很明确得了，自己按照其讲解大体实现了一遍，感觉还不错。其算法的效率在于next表的建立上，宗旨就是避免朴素匹配算法中的冗余回溯问题。还是直接上代码吧。
#ifndef ALGKMP_H__
#define ALGKMP_H__
static class KMP
{
public:
KMP(char *pattern, char *target, int &index);
~KMP();
private:
int patternLen;
int *next;
void calNextTable(char *pattern);
}; KMP::KMP(char *pattern, char *target, int &index)
{
patternLen = strlen(pattern);
next = new int[patternLen];
calNextTable(pattern);
index = ;
while(index < strlen(target) - patternLen)
{
int flag = ;
for (; flag < patternLen; flag++)
{
if (pattern[flag] != target[index + flag])
{
index = index+ + flag - next[flag];
break;
}
}
if (flag == patternLen)break;
}
if (index == strlen(target) - patternLen)index = -;
}
KMP::~KMP()
{
delete[] next;
}
void KMP::calNextTable(char *pattern)
{
//int *f = new int[patternLen];
//f[0] = 0;
next[] = ;
/*--------------待优化----------------------*/
for (int i = ; i < patternLen; i++)
{
int value = ;
for (int k = ; k < i - ; k++)
{
int flag = ;
for (flag = ; flag <= k; flag++)
{
if (pattern[flag] != pattern[i - - k + flag])break;
}
if (flag == k + )value = k + ;
} next[i] = value + ;
for (int j = ; j < i; j++)
{
if (pattern[i] == pattern[j])
{
next[i] = next[j];
break;
}
}
}
//delete f;
}
#endif
demo:
#include"iostream"
#include"AlgKMP.h"
using namespace std;
int main(int argv, char *argc[])
{
int index;
KMP("BBBC", "BBBBCDEFG", index);
cout <<index<< endl;
return ;
}