首页 > 代码库 > KMP算法 学习笔记
KMP算法 学习笔记
kmp算法在很多人看来是如此的厉害,很早之前就学过了,但是各种看不懂把我拦住了,现在重新拾取,来写一下个人的学习总结。
kmp看毛片算法(小甲鱼教的)(在这给小甲鱼做个广告,我个人看来小甲鱼讲的数据结构很好,很有趣。个人创业不容易,希望大家多多支持www.fishc.com小甲鱼,我跟小甲鱼素不相识,只是有用的东西大家分享)
好了言归正传。
如果你之前看过kmp算法没有看懂希望在这不要带着一种恐惧感,如果你没看过那是更好。
网上有很多详细教程,但是大部分都很啰嗦,容易把人看晕。
kmp算法没有什么难的,你只要记住一点:kmp算法就是提前处理一下我们要找的字符串。
我们怎样来处理要找的字符串呢?
举个例子就是....例子好复杂。
我直接说视频吧。我想没有很么能比视频讲的明白了 。
视频的下载地址在这里
http :
//pan.baidu.com/s/1eQtceWE
好了,继续说,视频上讲的简单明了。很适合我们的思维。
在这里补充一点就是,在视频中小甲鱼的
else { j=next[j]; }
没有讲明白,我给大家补充一下我的想法。(当大家看了视频就会知道是哪里了)。
就是当s[i]!=s[j]的时候要将j返回到next[j]所指的位置,大家可以这样来想,我们的next的数组是干嘛的,不就是为了不匹配的时候我们向前来跳转的嘛,这里就直接用上就行了。可能我说的也有一点模糊,但是大家想一下,现在把前面这个字符串当做是要找的字符串,后面这个是那个s串(也就是长的串(这样说不太好,但是容易理解)),这样我们找不到,自然就要回到next【j】了。对吧。
好了下面贴上看完视频后自己还原的代码:
#include<iostream> #include<string> using namespace std; //kmp算法 //next数组的构建 void get_next(string s,int * next) { int i=0; int j=-1; next[0]=-1; while(i<s.size()) { if(j==-1||s[i]==s[j]) { i++; j++; next[i]=j; } else { j=next[j]; } } } int main() { string s,t; cin>>s>>t; int next[1000]; get_next(t,next); //下面是kmp算法的实现 我是从开头开始查询的 返回了位置。 int i=0,j=0; int ssize=s.size(); int tsize=t.size(); while(i<ssize&&j<tsize) { if(j==-1||s[i]==t[j]) { i++; j++; } else { j=next[j]; } } if(j==t.size()) { cout<<i-tsize+1<<endl; } else { cout<<"no"<<endl; } system("pause"); }其中存在视频中所说的优化问题下面来进行优化:
#include<iostream> #include<string> using namespace std; //kmp算法 //next数组的构建 void get_next(string s,int * next) { int i=0; int j=-1; next[0]=-1; while(i<s.size()) { if(j==-1||s[i]==s[j]) { i++; j++; if(s[i]==s[j]) next[i]=next[j]; else next[i]=j; } else { j=next[j]; } } } int main() { string s,t; cin>>s>>t; int next[1000]; get_next(t,next); //下面是kmp算法的实现 我是从开头开始查询的 返回了位置。 int i=0,j=0; int ssize=s.size(); int tsize=t.size(); while(i<ssize&&j<tsize) { if(j==-1||s[i]==t[j]) { i++; j++; } else { j=next[j]; } } if(j==t.size()) { cout<<i-tsize+1<<endl; } else { cout<<"no"<<endl; } system("pause"); }
好了!
感谢自己坚持。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。