简介

  • 从一个字符串中查找另一个字符串的位置
  • 会利用字符串匹配过程中失败和成功的信息，减少字符串查找比较的字数

前置知识

  • 前缀：包括一个字符串第一个字符的子串；真前缀指除了它本身的所有前缀
  • 后缀：包括一个字符串最后一个字符的子串；真后缀指除了它本身的所有后缀

核心思想

  • 在s1中查找s2出现的位置，我们将s1称作待匹配串，s2称作模式串
  • 当一次匹配失败时，找到模式串中失配位置，此时我们可以知道，失配位置之前的这个子串是匹配成功的，我们将这个子串命名为s3
  • 接下来我们考虑如何向后移动子串，寻找下一个可能匹配的位置，现在我们已清楚的是：s3就是待匹配串的一面镜子，我们接下来尝试去匹配的部分就在它的后缀之中，而在模式串中我们首先要确保它的前缀与待匹配串适配，如果接下来我们在s3中寻找它的前缀可以和它的后缀匹配的最长部分（长度为l），并在下一次移动中使s3的前缀与移动之前的这个后缀重合，这样就找到了最近的一个可能匹配的位置
  • 我们想想为什么这是最近的，即证移动到它之前的位置都一定无法匹配成功：如果移动到之前的位置可以匹配成功，那么意味着s3的前缀可以和后缀匹配成功的长度要大于l，但l已经是我们之前找到的最大长度，故产生矛盾，得证
  • 再代入极端条件理解一下：若b=0，则下次从s2[0]开始匹配；实际情况下，找不到前缀与后缀的重叠部分，则无法找出已经可以匹配的前缀部分，则要从s2的开头开始匹配。符合实际情况
  • 不难发现前面所说的s3就在模式串的前缀集合中。现在我们只需解决子问题：寻找模式串中所有前缀的真前缀与真后缀最长匹配部分，这部分称为最长border

子问题

寻找模式串中所有前缀的真前缀与真后缀最长匹配部分

令模式串 0~i 子串的最长 border 的长度为 b_i。
我们可以找到 b_i 与 b_{i-1} 的递推关系：

  • 如果 s[i] = s[b[i-1]]，则 b[i] = b[i-1] + 1。

  • 否则，我们要寻找 0~(i-1) 中次短 border 的长度，看能否匹配。又

    s[0] ~ s[b[i-1]-1] = s[i-b[i]] ~ s[i-1]

    s[0]s[i-1] 的后缀等于 s[0]s[b[i-1]-1] 的真后缀，
    前缀也是 s[0]s[b[i-1]-1] 的真前缀，
    故问题转化为寻找 s[0]s[b[i-1]-1] 的最长 border（注意此处所说的前缀、后缀都指要找的次短 border），
    亦即 b[b[i-1]-1]，再看 s[i] 是否等于 s[b[b[i-1]-1]]，继续迭代即可。

这样我们就可以递推地标出数组 b！

代码实现

  • 代码实现中，将模式串的指针设为j，待匹配串的指针设为i，指向要匹配的字符，若失配则将j设置为b[j-1], 从这一位开始匹配即可，因为前面的都已匹配好
  • 洛谷P3375【模板】[[KMPhttps://www.luogu.com.cn/problem/P3375]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000010
using namespace std;
int b[MAXN], len1, len2;
string s1, s2;
int main() {
    cin >> s1 >> s2;
    len1 = s1.size(), len2 = s2.size();
    int j = 0;
    for(int i=1; i<len2; i++) { // 不能从0开始，b[0]=0
        // 计算数组b, j = b[i-1]
        while(j>0 && s2[i]!=s2[j]) {
            j = b[j-1];
        }
        if(s2[j] == s2[i]) j++; // 匹配上了 
        b[i] = j;
    }
    j = 0;
    for(int i=0; i<len1; i++) {
        while (j>0 && s2[j] != s1[i])
        {
            j = b[j-1];
        }
        if(s1[i]==s2[j]) j++; // 匹配上了这一位，开始匹配下一位
        if(j == len2) {
            cout << i-len2+2 << endl;
            j = b[j-1];
        }
    }
    for(int i=0; i<len2; i++) {
        cout << b[i] << " ";
    }
    cout << endl;
    return 0;
}