最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

KMP算法学习笔记

来源：博客园

总算把这个东西搞懂了......

KMP是一个求解字符串匹配问题的算法。


(资料图片)

这个东西的核心是一个\(next\)数组，\(next_i\)表示字符串第\(0\sim i\)项的相同的前缀和后缀的最大长度。

这里的前缀和后缀概念略有不同，如 DUCK的前缀为 D,DU,DUC,后缀为 K,CK,UCK，不包含 DUCK本身。

再举一个例子，假设有字符串 DUCKDUCK,则相同的前缀和后缀的最大为 DUCK，因此\(next_7\)值为 \(4\)。

那么怎么求解呢？

对于\(i\),我们知道了\(S_{0\sim next_{i-1}-1}\)和\(S_{i-next_i-1\sim i-1}\)是一样的，如果\(S_{next_{i-1}}=S_i\)就最好，\(next_i=next_{i-1}+1\)。

如果不是怎么办？我们设\(t=next_{i-1}-1\),由于\(S_{0\sim next_{i-1}-1}\)和\(S_{i-next_i-1\sim i-1}\)是一样的，所以在两者的内部，肯定都会有一对长度为\(next_t\)大小的相同的前缀和后缀。

那么，我们考虑新的这个前缀后面等不等于\(s_i\)，等于则问题解决，否则故技重施，再找出一个前缀。

可以手动模拟理解一下。

nxt[0]=-1;for(int i=1;i

有了这个\(next\)就方便许多了，我们将短的那个字符串的\(next\)算出，如果匹配失败，可以找出前面的，与后缀一样的部分，顶上来匹配，节省时间。

时间复杂度是\(O(|S|)\)的，也就是\(O(n)\)级别。

int i=0,j=0;while(i

关键词：