这是我在google 上的代码搜索出来的KMP算法我觉得写的还可以啊，自己拿来学学。 KMP.h#ifndef _KMP_H_ #define _KMP_H_ #ifdef __cplusplus extern "C" { #endif /* __cplusplus */ extern int KMP(const char* strPattern, int len, const char* strTarget); extern void KMP_end(); #ifdef __cplusplus } #endif /* __cplusplus */ #endif 申明一下。这个KMP是在字典程序中的一段。所以这个他用来申明的外部函数。KMP.cpp#include <stdio.h> #include <stdlib.h> #include <string.h> #include "kmp.h" static int* prefix = NULL; static int max_size = 0; static void GetPrefixValue(const char* strPattern, int iPatternLen) { if (iPatternLen>max_size) { prefix = (int*)realloc(prefix, iPatternLen*sizeof(int)); max_size = iPatternLen; } int i, j; /* i runs through the string, j counts the hits*/ i = 1; j = 0; prefix[0] = 0; while(i<iPatternLen) { if(strPattern[i] == strPattern[j]) { prefix[i] = ++j; } else { j = 0; prefix[i] = j; } i++; } } static int KMPStringMatch(const char* strPattern, int iPatternLen, const char* strTarget, int iTargetLen) { int j =0; int i; for (i=0;i<iPatternLen;i++) { while ((strPattern[i] != strTarget[j]) && (j > 0)) j = prefix[j-1]; if (strPattern[i] == strTarget[j]) j++; if (j == iTargetLen) return i - j + 1; } return -1; } int KMP(const char* strPattern, int len, const char* strTarget) { GetPrefixValue(strPattern, len); return KMPStringMatch(strPattern, len, strTarget, strlen(strTarget)); } void KMP_end() { free(prefix); prefix=NULL; max_size=0; } 其实我们学习中要好好的利用googe，百度等的搜索来学习。不过我很喜欢GOOGLE的这个代码搜索他可以让你找到很多的代码去学习。

评论