KMP
KMP是一种非常有用的算法，可以将字符串匹配的复杂度由 \(O(nm)\) 降到 \(O(n+m)\)
朴素算法
学过语言就会朴素算法，这里只给出伪代码：
for(i=0->n-1){
for(j=i>m-i){
if(s[i]!=s[j])goto fg;
}
cout<<i<<endl;
fg:;
}
时间复杂度 \(O(nm)\)。
KMP
KMP是基于DP的一种字符串匹配算法。
他先扫一遍模式串，建立 next 数组。
再通过 next 数组自动判断可以文本串当前位置能匹配到模式串第几个。
这听起来很神奇，但做起来更神奇。
图解
建立失配指针
假设模式串为abcabc
我们令红色箭头为匹配后的推进，蓝色箭头为失配后的推进。
next[0]
只有a才能推进，所以只有next[0]如果相同则推进至 1
next[1]
只有b才能推进，所以只有next[1]如果相同则推进至 2
next[2]
同理，只有c才能推进，所以只有next[2]如果相同则推进至 3
next[3]
从这里开始推进就不讲了。
当a失配时，我们看到它与前面的a有相同的前缀，所以a的失配指针为0
next[4]
当b失配时，我们看到它与前面的ab有相同的前缀，所以b的失配指针为1
next[5]
当c失配时，我们看到它与前面的abc有相同的前缀，所以c的失配指针为3
结果
结果如下图：
匹配
假设文本串为abcdababcabc。
黑色为当前走的箭头。
abc
直接跳到了3
d
失配了，因为模式串中没有一个d，所以直接跳到了0
