字符串算法都是毒瘤的
一.kmp算法的用处
在文本串中查找模式串的位置，数量
文本串：要在这个字符串查找模式串
模式串：在文本串中查找的字符串
全是废话
二.kmp算法的思想
话说kmp好像是3个发明者的首字母
如果暴力在文本串中查找模式串，时间期望复杂度是O(N+M)，N，M为文本串，模式串的长度，但经过毒瘤出题人的构造数据，暴力会被卡成O(NM)
kmp的精髓在于每次失配时，珂以不用从头开始
这样说有点迷，我们结合数据来看一下：
模式串：abcab
文本串：abcacababcab
首先前4位都匹配成功，但是，第5位出现了不同
这时，我们不要把模式串往右移1位，而是要移3位
模式串： abcab
文本串：abcacababcab
但有时候不止1位重复，而是有好几个字符相同
模式串：abcabc
文本串：abcabdababcabc
匹配到第6位时失配了，我们珂以把模式串往右移3位
模式串： abcabc
文本串：abcabdababcabc
那么现在已经很明了了， kmp匹配的重头戏就在于用失配数组来确定当某一位失配时，我们可以将前一位跳跃到之前匹配过的某一位。而此处有几个先决条件需要理解：
1.我们的失配数组应当建立在模式串意义下，而不是文本串意义下。因为显然模式串要更加灵活，在失配后换位时，更灵活简便地处理。
2.如何确定位置
首先我们要明白，基于先决条件1而言，我们在预处理时应当考虑当模式串的第 i 位失配时，应当跳转到哪里.因为在文本串中，之前匹配过的所有字符已经没有用了——都是匹配完成或者已经失配的，所以我们的 kmp 数组（即是用于确定失配后变化位置的数组，下同）应当记录的是：
在模式串 str1 中，对于每一位 str1(i) ,它的kmp数组应当是记录一个位置 j, j≤i
并且满足 str1(i)=str1(j) 并且在 j!=1时理应满足 str1(1)至str1(j-1) 分别与 str(i-j+1)~str1(i-1) 按位相等
3.从前缀后缀来解释 kmp匹配 :
首先解释前后缀(因为太简单就不解释了 qaq）：
给定串：ABCABA
前缀：A,AB,ABC,ABCA,ABCAB,ABCABA
后缀：A,BA,ABA,CABA,BCABA,ABCABA
其实刚才的移位法则就是对于模式串的每个前缀而言，用kmp数组记录到它为止的模式串前缀的真前缀和真后缀最大相同的位置（注意，这个地方没有写错，是真的有嵌套 qaq ）。然而这个地方我们要考虑“模式串前缀的前缀和后缀最大相同的位置”原因在于，我们需要用到kmp数组换位时，当且仅当未完全匹配。所以我们的操作只是针对模式串的前缀——毕竟是失配函数，失配之后只有可能是某个部分前缀需要“快速移动”。所以这就可以解释kmp匹配中前后缀应用的一个特点：
kmp匹配中前后缀不包括模式串本身,即只考虑真前缀和真后缀,因为模式串本身需要整体考虑，当且仅当匹配完整个串之后；而匹配完整个串不就完成匹配了吗 qaq
三.kmp匹配的代码实现
1.kmp[i] 用于记录当匹配到模式串的第 i 位之后失配,该跳转到模式串的哪个位置，那么对于模式串的第一位和第二位而言，只能回跳到 1，因为是kmp匹配是要将真前缀跳跃到与它相同的真后缀上去（通常也可以反着理解），所以当 i=0或者 i=1时,相同的真前缀只会是 str1(0)这一个字符，所以 kmp[0]=kmp[1]=1。
2.算出kmp数组之后匹配就比较简单
k=0;
//k可以看做表示当前已经匹配完的模式串的最后一位的位置
//如果楼上看不懂，你也可以理解为j表示模式串匹配到第几位了
for(register int i=0;i<len1;++i)
{
while(k&&a1[i]!=a2[k])
k=kmp[k];
//如果失配 ，那么就不断向回跳，直到可以继续匹配
k+=a1[i]==a2[k]?1:0;
//如果匹配成功，那么对应的模式串位置向后移
if(k==len2)
printf("%d
",i-len2+2),k=kmp[k];
//匹配成功，继续匹配
}
3.如何求kmp数组，我们用模式串自己匹配自己
int k=0;
for(register int i=1;i<len2;++i)
{
while(k&&a2[i]!=a2[k])
k=kmp[k];
//此处判断j是否为0的原因在于，如果回跳到第一个字符就不 用再回跳了
kmp[i+1]=a2[i]==a2[k]?++k:0;
}
完整代码，很简短，但其内涵还是需要细细理解
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
char a1[N],a2[N];
int kmp[N];
int main()
{
scanf("%s%s",a1,a2);
kmp[0]=kmp[1]=0;
int len1=strlen(a1),len2=strlen(a2);
int k=0;
for(register int i=1;i<len2;++i)
{
while(k&&a2[i]!=a2[k])
k=kmp[k];
kmp[i+1]=a2[i]==a2[k]?++k:0;
}
k=0;
for(register int i=0;i<len1;++i)
{
while(k&&a1[i]!=a2[k])
k=kmp[k];
k+=a1[i]==a2[k]?1:0;
if(k==len2)
printf("%d
",i-len2+2),k=kmp[k];
}
for(register int i=1;i<=len2;++i)
printf("%d ",kmp[i]);
return 0;
}
相关题目