void CreatPreFix(char pattern[],int prefix[],int n) { int i=0,j=1; prefix[0]=0; while(j<n) { if(pattern[i]==pattern[j]) prefix[j++]=++i; else if(i>0) i=prefix[i-1]; else prefix[j++]=0; } } void MovePreFix(int prefix[],int n) { for(int i=n-1;i>0;i--) prefix[i]=prefix[i-1]; prefix[0]=-1; } void Kmp_Search(char text[],char pattern[],int n,int prefix[]) { //text[i] len[text]=m; //pattern[j] len[pattern]=n; int m=strlen(text); int i=0,j=0; while(i<m) { if(j==n-1&&text[i]==pattern[j]) { printf("Found pattern at %d\n",i-j); j=prefix[j]; } if(text[i]==pattern[j]) { i++; j++; } else { if(j==-1) { j++; i++; } j=prefix[j]; } } } int main(){ char pattern[]="ABABCABAA"; char text[]="ABABABCABAA"; int prefix[9]; int n=9; CreatPreFix(pattern,prefix,n); MovePreFix(prefix,n); Kmp_Search(text,pattern,n,prefix); }
下面是伪代码讲解
KMP算法第一步需要求出字串的prefix前缀式 首先将prefix的第一项设为0 在pattern循环完毕之前 进行pattern[j]和pattern[i]进行比较 if 相等 将此时的i值向右移动一格，i自增 将此时的自增过后的i值赋值给pattern[j]所对应的prefix[j]表 j向右移动 if !相等 如果此时的i值是大于零的 将i项左边一项的prefix值附给i，让i的位置移动到prefix[i-1]的值对应的位置上 如果不相等，而且此时的i已经是0了，如果再-1就变成负数，会让i指向一个不知道的地方 则此时的prefix[j]对应的值为0 将求得的prefix整体向右移动，第一项补-1 开始Kmp_Search算法 首先设定text串(一堆乱七八糟的文本串)的长度为m，用i在text中遍历 pattern串(目标查找串)的长度为n，用j在其中遍历 while(i<m)//在整个文本串中遍历，寻找目标串 if (目标串已遍历到最后&&文本串[j]的字符等于目标串[i]) printf出目标串在文本串中第一次出现的位置 j重新回到prefix[j]所指向的位数 if(目标串[i]==文本串[i]) i++；j++；//i,j整体后移，开始比较下一项是否相等 else//不相等 if既不相等，而且当前的j的prefix[j]的值为-1 i++；j++；i，j整体后移，跳过当前的字符串开始进行下一个字符的比对 否则 pattern当前的j回到prefixtab[j]所指向的pattern的位置
这种简化版的代码容易理解，以后抽时间讲解时如何实现的
原文：https://www.cnblogs.com/oldfish123/p/12864201.html