如果你不了解哈希，建议先观看本蒟蒻的另一篇博客，对哈希有一定的理解 哈希大法吼
KMP算法，别名烤馍片或者看毛片，由烤馍片男子天团三位神犇同时发现的一种强大的单模式串匹配算法
通俗翻译即寻找一个模式串是否在一个文本串中出现过，出现过几次，出现的位置等等。
用于更快速地将口吐芬芳的用户禁言
首先我们分析一般的单模式串匹配算法：
1.暴力枚举法：
每次依次匹配两个字符串的每一位，这样如果是aaaaaaa....这种字符串的话复杂度就会高达O（n*m）；
2.哈希优化法：
预处理出模式串和文本串的哈希，枚举一个起点用哈希O（1）判断是否相等，时间复杂度O（文本串）；
好像挺快的啊，那还学什么KMP啊，好了本文到此结束。
既然哈希优化暴力枚举即可达到O（文本串）的优秀复杂度我，为何还要学习复杂度为O（文本串+模式串）的KMP算法呢？这与KMP的实现原理有关
仔细观察暴力枚举的漏洞，如果一个模式串在当前位置匹配完毕（无论失败成功），模式串首部只能前进一位，而中间可能包含大量无用匹配，这些匹配是之前已经确认失败的。
而KMP思想的先进之处在于，每次模式串在当前位置匹配完毕之后，充分利用之前信息，将已经匹配成功的部分跳过从而减少时间复杂度
举个栗子：
文本串：abcabqwq
模式串：abcabe
在这两种模式串匹配过程中，显然模式串与文本串在匹配到第六位的时候会失配，在一般的算法中下一步会变成酱紫
文本串：abcabqwq
模式串： abcabe
然而我们观察到，如果文本串bcab...能够和模式串abcabe匹配上，那么模式串的e之前的四位字符应该与开头的四位字符相同才对，毕竟e之前的四位已经匹配成功了，但显然是不同的。
继而我们得出一个结论：如果一个字符串移动后能够匹配上，那么已经匹配成功的子串的后几位字符应该与开头的几位字符相同。
在模式串abcabe中，匹配成功的子串abcabc中只有ab与开头部分相同，那么我们大可以直接将ab移动到相应的位置上去：
文本串：abcabqwq
模式串： abcabe
如果移动以后仍然不能匹配成功呢？那么只要重复这个过程，直到下一位可以匹配上，或者模式串已经不能通过这种方式移动了，再向右继续匹配。
为了不遗漏匹配，我们必须保证所有可能匹配成功的地方都扫过一遍，也就是说，我们模式串向右移动的距离应该尽可能短，这是为了保证正确性。
所以我们要找模式串中每个前缀的最大后缀等于前缀（注意不能相等哦！），qwq有点拗口希望仔细理解一下，然后开一个数组（我们称为失配数组）记录这个后缀的长度，方便每次跳串（跳串什么鬼啦
下文中我们称这个最大后缀等于前缀中的后缀为失配后缀，前缀为失配前缀，失配数组为nxt，文本串为s1，模式串为s2
模式串前缀：a ab abc abca abcab abcabe
失配数组： 0 0 0 1 2 0
失配数组获取：
我们设置两个指针，i 负责扫描整个模式串，t 负责指向当前失配前缀。
初始时刻 t 应滞后 i 一个位置，毕竟不能相等嘛qwq
然后我们将要进行的是一个模式串自己匹配自己的过程，将 i 与 t 向右推进，每次失配时t2直接利用已经处理出来的失配数组向回跳
栗子：
模式串：a b a c a b
t i 初始状态，nxt [ 1 ] = 0； 然而 s2 [ i+1 ]与s2 [ t+1 ]不匹配，且t无法向前跳，所以t不移动，++i；
模式串：a b a c a b
t i 此时nxt [ 2 ] = 0；，发现 s2 [ i+1 ]与s2 [ t+1 ] 匹配，++t；，++i；
模式串：a b a c a b
t i nxt [ 3 ] =1，下一步s2 [ i+1 ]与s2 [ t+1 ]不匹配，t沿着nxt [ t ]数组向回跳，直到下一位匹配或者无法继续跳。
实现方法有两种，总的来说第二种性质更优秀，但第一种更容易理解（个人认为），在这里两种方法都展示出来
inline void get_nxt()//第一种
{
int t1=0,t2;
nxt[0]=t2=-1;
while(t1<len2)
{
if(t2==-1||s2[t1]==s2[t2])
nxt[++t1]=++t2;
else
t2=nxt[t2];
}
}
inline void get_nxt()//第二种
{
t=0;
for(int i=1;i<len2;++i)
{
while(t&&s2[t]!=s2[i]) t=nxt[t];
t+=(s2[t]==s2[i]);
nxt[i+1]=t;
}
}
inline void get_nxt()//第二种下标从1开始的写法
{
t=0;
for(int i=2;i<=len2;++i)
{
while(t&&s2[t+1]!=s2[i]) t=nxt[t];
t+=(s2[t+1]==s2[i]);
nxt[i]=t;
}
}
匹配时更加简单，匹配成功就前进一位，失败就跳失配数组
inline void kmp()//第一种 对应
{
int t1=0,t2=0;
while(t1<len1)
{
if(t2==-1||s1[t1]==s2[t2])
t1++,t2++;
else t2=nxt[t2];
if(t2==len2)
{
//匹配成功，其他操作
t2=nxt[t2];
}
}
}
inline void kmp()//第二种 对应
{
t=0;
for(int i=0;i<len1;++i)
{
while(t&&s2[t+1]!=s1[i]) t=nxt[t];
t+=(s2[t+1]==s1[i]);
if(t==len2-1)
{
//匹配成功，其他操作
}
}
}
inline void kmp()//第二种 下标 1 开始
{
t=0;
for(int i=1;i<=len1;++i)
{
while(t&&s2[t+1]!=s1[i]) t=nxt[t];
t+=(s2[t+1]==s1[i]);
if(t==len2)
{
//匹配成功，原地爆炸
t=nxt[t];
}
}
}
看到这里相信各位有所感触：KMP算法精华在于nxt数组，它在O（文本串+模式串）的时间内还求出了模式串每个前缀的 最大后缀等于前缀 这一重要信息，相比之下，匹配文本倒是其次（毕竟单纯的匹配的话哈希爆搞也能搞过），该算法一些优秀的扩展大部分也是基于nxt数组的性质来实现的。
给定长度为n的字符串，求字符串每个前缀的最小后缀等于前缀。
分析：这里设计到一个性质：失配前缀的后缀仍是失配后缀的一部分（毕竟失配前缀完全等同于失配后缀嘛）
由于这条性质，我们只要一直沿着nxt数组向前跳，直到nxt [ t ] = 0，考虑到复杂度问题，我们在路径上加一个类似并查集的路径压缩操作；
求一个字符串最多由几个循环节拼成
分析：还记得我们的神仙结论吗？判断一个字符串[ l , r ]是否存在一个长度为d的循环节，只需判断 [ l+d , r ] 和 [ l , r-d ] 是否相等。
再联想nxt数组的内容：最大后缀等于前缀的长度。
答案就呼之欲出了！
最小循环节长度 res = len - nxt [ len ] ；
最多循环节数量 ans = len / res ；
这个神仙结论证明有点子麻烦我不想在这里写emmmmm，大家脑补一下好了。
最少添加多少字符能获得循环节
分析：首先若补充或补充最少，找到最小循环节一定是最优的，这里利用上面的最小循环节姿势。
分类讨论： 若nxt [ len ] 等于0，则需要补充 len 个字符
若nxt [ len ]不为0 若存在循环节，即len%（len - nxt [ len ]）== 0 ，不需要补充字符
不存在循环节，那么至少用补充（len - nxt [ len ]）- （len % （len - nxt [ len ]））（最小循环节长度减去已经存在而不足的长度）
原文：https://www.cnblogs.com/knife-rose/p/11240828.html