核心就是两步
1 计算next数组，对pattern串进行分析。 复杂度为o(n)
2 对target串进行查找。复杂度为 o(m+n)
所以总共的复杂度为 o(m+n)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int *GetNextArray(const char *const pattern, size_t length) {
// Create next array in heap and initialize its value to zero
int *next = new int[length]();
if (NULL == next)
{
return NULL;
}
for (size_t i=1; i<length; ++i)
{
if ( (0 != next[i-1]) &&
(pattern[next[i-1]] == pattern[i]) )
{
next[i] = next[i-1] + 1;
continue;
}
if (pattern[0] == pattern[i])
{
next[i] = 1;
}
else
{
next[i] = 0;
}
}
return next;
}
namespace {
const int Error_Get_Next_Array = -1;
const int START_INDEX = 0;
}
int KMP(const char *const target, const char *const pattern) {
size_t size_pattern = strlen(pattern);
size_t size_target = strlen(target);
int *next = GetNextArray(pattern, size_pattern);
if(NULL == next) {
return Error_Get_Next_Array;
}
int index_target = START_INDEX, index_pattern = START_INDEX;
while( (index_target<size_target) &&
(index_pattern<size_pattern) ) {
if (target[index_target] == pattern[index_pattern]) {
++index_pattern;
++index_target;
} else {
if (START_INDEX == index_pattern) {
++index_target;
continue;
}
index_pattern = next[index_pattern-1];
}
}
// delete next
delete [] next;
if (index_pattern == size_pattern) {
return index_target - size_pattern;
} else {
return -1;
}
}
int main()
{
const char *const pattern = "abaabcac";
const char *const target = "acabaabaabcacaabc";
size_t length = strlen(target);
int index = KMP(target, pattern);
if(Error_Get_Next_Array == index) {
cout<<"Error happened when try to calculate next array"<<endl;
return 0;
}
cout<<"The result is:"<<endl;
cout<<target<<endl;
for (size_t i=0; i<index; ++i)
{
cout<<" ";
}
cout<<pattern<<endl;
return 0;
}
只需对内存分配改一下，就是C代码了 PS C代码中的堆分配函数calloc(numElements ，sizeOfElement)； // 两个参数，并将内存初始化为0
malloc(numElements *sizeOfElement) ； // 一个参数，不初始化内存
