算法細節詳見點擊打開鏈接和點擊打開鏈接

#include <stdio.h> #include <stdlib.h> #define N 7 #define M 15 void showpset(int* a); void cal_pset(char* a, int* p,int n); int KMP(char* a,char* b,int* P);int main(void) {char a[M]={'a','b','a','c','a','b','a','a','b','a','b','a','c','b','d'};char b[N]={'a','b','a','b','a','c','b'};int P[N]={0};int i=1;int index=-1;cal_pset(b,P,N);index=KMP(a,b,P);//showpset(P);printf("%d ",index);system("pause");return 0; }int KMP(char* a,char* b,int* P) {int i=0,j=0;int flag=0;while(i<M){while(a[i]==b[j]){if(j==N-1){flag=1;break; }if(i<M-1 && j<N-1){i++;j++;}else{flag=2;break;}}if(a[i]!=b[j]){if(j==0 || (j!=0 && P[j-1]==0)){while(i<M && a[i]!=b[0]){i++;}j=0;}else{j=P[j-1];}}if(flag==1){return i-j;}if(flag==2){return -1;}}return -1; }void cal_pset(char* a, int* p,int n) {int i=1;while(i<n) //生成P矩陣{int j=0;while(a[j]==a[i]){p[i]=p[i-1]+1;j++;i++;}p[i++]=0;} }void showpset(int* a) {for(int i=0;i<N;i++){printf("%d ",a[i]);}return ; }

?

轉載于:https://www.cnblogs.com/hrhguanli/p/4029732.html

總結

以上是生活随笔為你收集整理的KMP算法---字符串匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。