前言:
去年2月份就学了kmp,3月份在学ac自动机的时候就忘了又去复习了下,现在在学数据结构,发现又忘了…我发现很多人都很容易忘掉这个算法,所以来写篇博客记录一下…最后吐槽下发明这个算法的人真是个天才(明明代码那么短,我却看不懂.
View in my own blog
想要记牢KMP,就得知道KMP是怎么来的:(以下来源百度百科)
KMP算法是一种改进的字符串匹配算法，KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
简单来说就是暴力算法的改进,减少暴力算法中不必要的匹配;
先来看看暴力算法:
//s为主串(长的字符串) t为模板串(短的字符串)
int BF(string s,string t)
{
int i=0,j=0;
while(it.size())return i-t.size();
return -1;
}
下面举个例子:(下面s串为主串,t为模板串)
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 主串 s | h< |