首页 > 代码库 > KMP算法_学习笔记
KMP算法_学习笔记
#include <cstdlib> #include <iostream> #include <cstring> using namespace std; int * buildNext(char *P){ size_t m=strlen(P), j=0; int* N=new int[m];//next表 int t=N[0]=-1; while(j<m-1){ if(0>t||P[j]==P[t]){ j++;t++; N[j]=(P[j]!=P[t]?t:N[t]);//改进 } else t=N[t]; } return N; } int match(char* P,char* T){ int* next=buildNext(P); int n=(int)strlen(T),i=0; int m=(int)strlen(P),j=0; while(j<m&&i<n) if(0>j||T[i]==P[j]){i++;j++;} else j=next[j]; delete [] next; return i-j;//返回首次匹配到到的位置下标(未找到则返回目标串长度) } int main(int argc, char *argv[]) { char T[1000]; char P[50]; while(cin>>T){ cin>>P; cout<<match(P,T)<<endl; } system("PAUSE"); return EXIT_SUCCESS; }
KMP算法_学习笔记
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。