KMP算法

Knuth-Morris-Pratt字符串查找算法(简称为KMP算法),此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符

上面这个算法需要先计算查找的子串的部分匹配表(Partial Match Table)

比如我们要在 bacbababaabcbab 字符串里查找 abababca

1.首先要计算 abababca 的部分匹配表 - 预处理

求出最长可能前缀也是最长可能后缀的长度值

a
前缀
后缀
value=0

ab
前缀 a
后缀 b
value=0

aba
前缀 a ab
后缀 a ba
value = 1(a)

abab
前缀 a ab aba
后缀 b ab bab
value=2(ab)

ababa
前缀 a ab aba abab
后缀 a ba aba baba
value=3(aba)

ababab
前缀 a ab aba abab ababa
后缀 b ab bab abab babab
value=4(abab)

abababc
前缀 a ab aba abab ababa ababab
后缀 c bc abc babc ababc bababc
value=0

abababca
前缀 a ab aba abab ababa ababab abababc
后缀 a ca bca abca babca ababca bababca
value=1(a)

按照下表,可以用数组表示

char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

第一次匹配在这里

bacbababaabcbab
 |
 abababca

这里这匹配成功1个,查表table[1-1]=0无需任何操作,继续往下匹配即可

bacbababaabcbab
    |||||
    abababca

此时,有5个字符匹配成功了,根据查表table[5-1]=3,也就是前缀的3个字符(aba)跟后缀的3个字符(aba)是一样的,此时只需要往前跳2(5-3)个字符,那么前缀的3个字符和后缀的3个字符就可以重叠,无需额外校验

bacbababaabcbab
    xx|||
      abababca

此时,有3个字符匹配成功,根据查表table[3-1]=1,也就是前缀的1个字符(a)和后缀的1个字符(a)一样,往前跳2(3-1)个字符

bacbababaabcbab
      xx|
        abababca

此时,子串长度大于剩余的串长度,匹配失败


预处理算法如下

pat[] = "abababca"

len = 0, i = 0
lps[0] = 0, i = 1

len = 0, i = 1
pat[len] != pat[i]
因为len == 0
lps[i] = 0, i = 2

len = 0, i = 2
pat[len] == pat[i] == 'a'(a), len = 1
lps[i] = len = 1(a), i = 3

len = 1, i = 3
pat[len] == pat[i] == 'b', len = 2
lps[i] = len = 2(ab), i = 4

len = 2, i = 4
pat[len] == pat[i] == 'a', len = 3
lps[i] = len = 3(aba), i = 5

len = 3, i = 5
pat[len] == pat[i] == 'b', len = 4
lps[i] = len = 4(abab), i = 6

len = 4, i = 6
pat[len] != pat[i], 因为 len > 0
len = lps[len-1] = 2

len = 2, i = 6
pat[len] != pat[i], 因为 len > 0
len = lps[len-1] = 0

len = 0, i = 6
pat[len] != pat[i], 因为 len == 0
lps[i] = 0, i = 7

len = 0, i = 7
pat[len] == pat[i] == 'a', len=1
lps[i] = len = 1(a), i = 8


linux c例子

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>

void compute_lps(char *pat, int n, int *lps)
{
    int len,i;

    len = 0;
    lps[0] = 0;
    i = 1;

    while (i < n) {
        if (pat[i] == pat[len])
            lps[i++] = ++len;
        else {
            if (len != 0)
                len = lps[len-1];
            else
                lps[i++] = 0;
        }

    }
}

void kmp_search(char *pat, char *txt, int *lps)
{
    int m,n,i,j;

    m = strlen(pat);
    n = strlen(txt);

    i = 0;  //txt 索引
    j = 0;  //pat 索引

    // 长度不够匹配的则退出
    while (n-i >= m-j) {
        if (pat[j] == txt[i]) {
            i++;
            j++;

            if (j == m) {
                printf("found at index %d\n", i - j);
                j = 0;
            }
        } else {
            if (j != 0)
                j = lps[j-1];
            else
                i++;
        }

    }

    printf("%d chars left\n", n-i);

}

void dump(int *lps, int n)
{
    int i;

    for (i = 0; i < n; i++) {
        printf("%d ", lps[i]);
    }
    printf("\n");
}

int main(int argc, char **argv) 
{
    if (argc != 3)
        return 0;

    char *pat = argv[2];
    char *txt = argv[1];
    int len = strlen(pat);

    int lps[len];

    compute_lps(pat, len, lps);
    //dump(lps, len);

    kmp_search(pat, txt, lps);

    return 0;
}


参考:

jakeboxer-kmp

geeksforgeeks-kmp


上一篇: 字符串搜索算法
下一篇: BM算法
作者邮箱: 203328517@qq.com