KMP字符串匹配算法实现

kmp字符串匹配算法C++代码实现

</pre><pre name="code" class="cpp">#ifndef __H_KMP_H__
#define __H_KMP_H__
#include <string>

//获得next数组
int _fill_next_array(char* comp, int len, int* next)
{
int i = 0;
int j = -1;
next[0] = -1;
while(i < len - 1)
{
if(j == -1 || comp[i] == comp[j])
{
++i;
++j;
if(comp[i] != comp[j])
{
next[i] = next[j];
}else{
next[i] = j;
}
}else{
j = next[j];
}
}
return 0;
}

//外部接口，返回一个字符串是否包含另一个字符串
bool is_contain_substring(char* src, char* comp)
{
if((NULL == src && NULL != comp) || (NULL != src && NULL == comp))
return false;
int len1 = strlen(src);
int len2 = strlen(comp);
if(len1 < len2)
return false;

int* next = new int[len2];
_fill_next_array(comp, len2, next);
int j = 0;
for(int i=0; i<len1; ++i)
{
if(src[i] == comp[j])
{
j++;
}else{
j = next[j]+1;
if(src[i] == comp[j])
{
j++;
}
}

if(j == len2)
return true;
}

return false;
}

#endif

调用：

#include "KMP.h"

int main()
{
std::cout << is_contain_substring("abcdabcabcdeabccba", "abcde") << std::endl;
return 0;
}