浅谈kmp
kmp算法老是忘，于是决定写一篇博客记录一下。
B站这个视频很易懂：https://www.bilibili.com/video/av11866460?from=search&seid=13585210173884155297
先说一下next数组的含义，next[i]就是字符串从0到i-1这个子串的最长相同前后缀的长度,一般习惯于把next[0]赋值为-1。
有了next数组，匹配起来就比暴力匹配快多了，虽然他的最坏情况和暴力是一样的。
kmp匹配时是移动模式串，每次匹配失败只要把模式串的next[i]位移到当前位置即可。
1.
2.
3.
大致上就是这样。（图画的好粗糙，嘤嘤嘤）
求next数组：
1 void getNext(char *p){ //比上边的nt数组往后一位 2 nt[0]=-1; 3 int i=0,j=-1; //j控制前缀,i控制后缀 4 int lp=strlen(p); 5 while(i<lp){ 6 if(j==-1||p[i]==p[j]){ 7 ++i;++j; 8 nt[i]=j; 9 } 10 else j=nt[j]; 11 } 12 }
求模式串在原串中出现过几次：
1 int kmp(char *t,char* p){ 2 getNext(p); 3 int i=0,j=0; 4 int lt=strlen(t),lp=strlen(p); 5 int ans=0; 6 while(i<lt){ 7 if(j==-1||t[i]==p[j]){ 8 i++; 9 j++; 10 } 11 else j=nt[j]; 12 if(j==lp) ans++; 13 } 14 return ans; 15 }
左边刷题右边 chat 效果很好