526互联

KMP 算法

发布时间 2024-01-09 16:41:39作者: Lemon-GPU

Question: Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

通常而言，这需要分为两个步骤：对模式字符串的预处理以及在目标字符串的搜索。

  1. 预处理——以ABABCABAB为例子
    lps，“longest proper prefix which is also suffix”数组的生成遵循着这么一个字如其名的原则。它的作用在于储存已知信息，这里的信息是可以重新开始匹配的index。已经匹配的部分的最长前后缀是可以重复使用的。我们给一个例子：

    初始化：
    lps_：0, 0, 0, 0, 0, 0, 0, 0, 0
    char：A, B, A, B, C, A, B, A, B

    a. 我们首先看字符串[0: 1]，可以略过，毕竟就一个字符

    b. 看字符串[0: 2]，可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB"}
    suffix: {"B", "AB"}
    match_: {False, --}
    因此lps_[1]为0

    c. 看字符串[0: 3], 可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB", "ABA"}
    suffix: {"A", "BA", "ABA"}
    match_: {True, False, --}
    因此lps_[2]为1（因为"A"是最长的匹配前后缀）

    d. 看字符串[0: 4]，可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB", "ABA", "ABAB"}
    suffix: {"B", "AB", "BAB", "ABAB"}
    match_: {False, True, False, --}
    因此lps_[3]为2（因为"AB"是最长的匹配前后缀）

    e. 看字符串[0: 5]，没有任何前缀和后缀是匹配的：
    prefix: {"A", "AB", "ABA", "ABAB", "ABABC"}
    suffix: {"C", "BC", "ABC", "BABC", "ABABC"}
    match_: {False, False, False, False, --}
    因此lps_[4]为0

    f. 看字符串[0: 6]，可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB", "ABA", "ABAB", "ABABC", "ABABCA"}
    suffix: {"A", "CA", "BCA", "ABCA", "BABCA", "ABABCA"}
    match_: {True, False, False, False, False, --}
    因此lps_[5]为1（因为"A"是最长的匹配前后缀）

    g. 看字符串[0: 7]，可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB", "ABA", "ABAB", "ABABC", "ABABCA", "ABABCAB"}
    suffix: {"B", "AB", "CAB", "BCAB", "ABCAB", "BABCAB", "ABABCAB"}
    match_: {False, True, False, False, False, False, --}
    因此lps_[6]为2（因为"AB"是最长的匹配前后缀）

    h. 看字符串[0: 8]，可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB", "ABA", "ABAB", "ABABC", "ABABCA", "ABABCAB", "ABABCABA"}
    suffix: {"A", "BA", "ABA", "CABA", "BCABA", "ABCABA", "BABCABA", "ABABCABA"}
    match_: {True, False, True, False, False, False, False, --} 因此lps_[7]为3（因为"ABA"是最长的匹配前后缀）

    i. 看字符串[0: 9]，可以发现所有的前缀、后缀和匹配如下：
    prefix: {"A", "AB", "ABA", "ABAB", "ABABC", "ABABCA", "ABABCAB", "ABABCABA", "ABABCABAB"}
    suffix: {"B", "AB", "BAB", "ABAB", "CABAB", "BCABAB", "ABCABAB", "BABCABAB", "ABABCABAB"}
    match_: {False, True, False, True, False, False, False, False, --}
    因此lps_[8]为4（因为"ABAB"是最长的匹配前后缀）

    最终，lps数组为： lps_: 0, 0, 1, 2, 0, 1, 2, 3, 4
    简化计算的方法也是有的，前后缀必须是连续的，那么我们完全可以接着使用上一次比较的信息来持续使用，这也就是为什么我们发现自身比较不匹配的时候，len = lps[len - 1]的原因了，而且此时i是不自增的。我们甚至会发现这个过程会在同一个地点持续多次。

  2. 比较
    跟上面比较类似，不过就是直接使用lps数组了。