KMP
一种字符串单模匹配算法。
原理
当模式串 \(s\) 与文本串 \(t\) 进行匹配时，容易想到的一种朴素做法就是将模式串的第一位与文本串的每一位进行试配。但是这样效率过低，容易被数据卡成 \(O(n^2)\)。
KMP 单模匹配算法引入了一个失配数组 border。
定义一个字符串的 border 为一个最长的字符串 \(s'\) 的长度，满足字符串 \(s'\) 既是 \(s\) 的真前缀，又是 \(s\) 的真后缀。
当失配时模式串 \(s\) 可以直接跳到 border 记录的位置，并且融入了动态规划的思想，避免了一次一次低效的匹配。
KMP 算法分 \(2\) 步：
-
将模式串 \(s\) 与其自己匹配，求出数组 border。
具体的，定义两个指针 \(i\) 和 \(j\)，表示此时 \(s[i-1-j+1 \sim i-1]\) 与 \(s[1 \sim j]\) 已经匹配成功的极大状态（以 \(i\) 和 \(j\) 结尾时无法实现更多字符的匹配），正在匹配 \(s[i]\) 与 \(s[j+1]\)。（指针 \(j\) 是匹配是横跳的指针，指针 \(i\) 从左到右移动）
若 \(s[i]\) 和 \(s[j+1]\) 失配，首先明确此时应该尽量让 \(s[i]\) 与 \(s[j+1]\) 实现匹配。那么指针 \(i\) 保持不变（因为是用 \(s[1 \sim j]\) 去匹配 \(i\) 之前的一段），去移动指针 \(j\)。
引理：当 \(s[i-1-j+1 \sim i-1]\) 与 \(s[1 \sim j]\) 匹配成功时，若 \(s[i]\) 和 \(s[j+1]\) 失配，则可能满足 \(s[i]\) 和 \(s[j+1]\) 匹配成功的最长字串的指针 \(j\) 的位置，应在 \(border[j]\) 处。
根据 border 的定义，反证法易证。
每次 \(i\) 进行匹配时，都会进行 \(border[i]\) 的标记，那么 \(border[j]\) 应在失配前就已经被标记了。所以，每次 \(s[i]\) 和 \(s[j+1]\) 失配时，就将指针 \(j\) 跳到 \(border[j]\)，直到 \(s[i]\) 与 \(s[j+1]\) 匹配成功。
-
将模式串 \(s\) 与文本串 \(t\) 进行匹配，与第一步类似。
例题
- 模板题 P3375 【模板】KMP 代码：
for(int i=2,j=0;i<=lenb;i++){//first step
while(j>0&&b[i]!=b[j+1]) j=fail[j];
if(b[i]==b[j+1]) j++;
fail[i]=j;
}
for(int i=1,j=0;i<=lena;i++){//second step
while(j>0&&(j==lenb||a[i]!=b[j+1])) j=fail[j];
if(a[i]==b[j+1]) j++;
f[i]=j;
if(f[i]==lenb){
printf("%d\n",i-lenb+1);
}
}