介绍

先上一道模板题：P3375 【模板】KMP字符串匹配

（难以想象这只是一道黄题） （而manacher竟然是蓝题）

大意就是给你两个字符串，问其中一个在另一个里面出现过几次。至于border什么的，当你写出KMP时，你也就算出来了

为方便理解，提前定义一下：模式串表示被拿去匹配的字符串，而主串则是另一个串。如样例中，模式串为"ABA"，主串为"ABABABC"

暴力？

（如果不想看暴力思想的可以直接跳到KMP介绍）

在样例解释中有这么一张图：

这张图展现的就是最朴素的暴力的过程：我们把模式串放在主串的每一位上，看看能不能匹配上。
具体实现就是维护两个指针： \(i\) 指主串，\(j\) 指向模式串，先让 \(i=0,j=0\)，接着不断 \(i++,j++\) 直到不匹配或者模式串匹配失败，然后再让 \(i=1,j=0\) 继续匹配，以此类推
假设模式串长度为 \(n\) ，主串长度为 \(m\) ，显然时间复杂度为 \(\Theta(nm)\)。

考虑优化：我们发现，第一次匹配完成之后，由于我们已知模式串第一位的A与主串第二位的B压根就不匹配，我们大可以直接跳过第二位，直接把模式串放在第三位上开始匹配。换言之，我们每一次在主串的 \(i\) 、模式串的 \(j\) 处匹配失败或结束匹配时，由于 \(j-1\) 是已经匹配好了的，所以我们可以把模式串 \(j-1\) 处的字符上一次出现的位置拎过来匹配。

比如模式串"ACBCA"和主串"ACBCBCA"，我们会在第五位 "A" 和 "B" 处匹配失败，这时候我们把上一位 "C" 上一次出现的位置拎过来，并继续匹配。等于在匹配"ACBCA"和"BCBCA"。

但是这么做有个问题：如果从 "C" 处开始往后匹配，我们会得到"ACBCA"与"BCBCA"能够匹配的错误答案。从开头处开始匹配，等于说每一次匹配失败又要从头开始匹配，稍微卡一卡数据（比如一串a），时间复杂度又退化成 \(\Theta(nm)\) 了

看起来这个"拎过来"的思想可以继续优化，那么，我们有没有一种办法，可以使字符串不从头匹配的同时，还能精准“拎”到正确的位置呢？

过不去那道题？
事实：它数据很大
而暴力是 \(\Theta(nm)\)
它最慢了！

介绍——KMP！

我们看这么一个例子：模式串 "ABBABA" 和主串 "ABBABBABA"，用 \(i\) 记录在主串中匹配到的位置，\(j\) 记录在模式串中匹配到的位置（为了方便，下标从零开始）

显然，我们这时候会在 \(i=5,j=5\) 时匹配失败，这时候我们不难发现：此时标蓝色的"AB"已经匹配成功了，而如果我们把模式串已经存在的红色的"AB"拎过来，就能直接和主串的 "AB" 匹配上。具体实现即为直接 \(i\) 不变，\(j\) 指向模式串第三位 "B"。此时，模式串位于 \(j\) 前面的已经全部匹配完成，现在继续匹配 \(i,j\)

我们不难发现：对于每一个 \(j\)，在该位置匹配失败后应 \(j\) 该跳转到的继续匹配位置为“对于模式串 \(0\) 到 \(j-1\) 构成的子串，对于所有 \(s\) 的一个非 \(s\) 本身的前缀 \(t\)，满足 \(t\) 同时也是 \(s\) 的后缀，长度最长的 \(t\) 的结尾往右一位”

我们可以用 \(next_{j-1}\) 来表示该位置，特别地，当 \(j=0\) 却仍然匹配失败时，我们直接让 \(i++\)。（换言之，我们每次匹配失败后都让 \(j=next_{j-1}\) 继续匹配直到 \(j=0\)）

我们用 \(s\) 表示模式串，两个下标 \(i,j\) ，其中 \(i\) 表示此时处理到了 \(next_i\)，\(j\) 则表示上一个 \(t\) 的结尾（即 \(next_{i-1}\)）。由于 \(next_0\) 不需要处理，所以初始化 \(i=1,j=0\)。我们分类讨论

第一种情况：\(s_i=s_j\) （红色位置为 \(j\)，蓝色位置为 \(i\)）

这时候就很愉快，直接让 \(j++,next_i=j\) 就好

第二种情况：\(s_i\neq s_j\)

这时候该怎么办呢？可以发现：我们在求 \(next\) 过程中，所做的实际上就是用模式串去匹配自己的后缀，那么根据 \(next\) 的定义，我们直接让 \(j=next_{j-1}\) ，直到 \(s_i=s_j\) 或 \(j=0\) 即可

kmp的核心思想就这些了，代码如下：

n=s1.size(),m=s2.size();
for(int i=1,j=0;i<m;i++){
	while(j>0&&s2[i]!=s2[j])
		j=nxt[j-1];
	if(s2[i]==s2[j])
		j++;
	nxt[i]=j;
}
for(int i=0,j=0;i<=n;){
	if(j==m)
		j=nxt[j-1]; //此时匹配结束，也就相当于在这位匹配失败了，所以j=nxt[j-1]
	if(s1[i]==s2[j]) 
                i++,j++;
	else if(j!=0) 
                j=nxt[j-1];
	else 
                i++;
}