代码部分

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "string.h"
#include "stdio.h"

/**
 * 获得目标串在某个位置匹配错误时，目标串应该跳转索引值，在pat[i]匹配错误时，i = lps[i-1]
 * @param pat 模式串
 * @param M 模式串的长度
 * @param lps(longest proper prefix which is also suffix) 对应索引值数组
 */
void GetLPSArray(const char *pat, int M, int *lps) {
    // length of the previous longest prefix suffix(pat每个字符对应len都是包括当前字符在内的前len个字符与pat前len个字符相等)
    int len = 0;
    // 第一个总是0
    lps[0] = 0;

    // i 指pat的下标
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            // 该情况的表现为pat[i]!=pat[0]
            if (len == 0) {
                lps[i] = 0;
                i++;
            } else {
                /**
                 * 回退。这里比较难理解，我们先看我们已知的
                 * 1. 在这里我们知道pat[i]与pat[len]匹配错误
                 * 2. pat[i-len...i-1] == pat[0...len-1]
                 * pat[0...len-1]字符所对应的len在之前就已算出，试想这么一个图像
                 *   目标串 a b c a b x
                 *
                 *   a b c -> a b c    -> a b c      -> a b c
                 *   a b x ->   a b x  ->     a b x  ->       a b x
                 */
                len = lps[len - 1];
            }
        }
    }
}

/**
 * 得到pat在txt第一次出现的下标
 * @param pat 模式串
 * @param txt 目标串
 * @return 如果没有匹配的返回-1，如匹配返回出现位置
 */
int IndexKMP(char *pat, char *txt) {
    // i为txt(目标串)下标，j为pat(模式串)下标
    int patI = 0, txtI = 0;
    // pat长度
    int patLen = strlen(pat);
    // txt长度
    int txtLen = strlen(txt);
    int lps[patLen];
    GetLPSArray(pat, patLen, lps);
    while (txtI < txtLen) {
        if (pat[patI] == txt[txtI]) {
            patI++;
            txtI++;
        }
        if (patI == patLen) {
            return txtI - patI;
        } else if (txtI < txtLen && pat[patI] != txt[txtI]) {
            if (patI != 0) {
                patI = lps[patI - 1];
            } else {
                txtI++;
            }
        }
    }
    return -1;
}

前言

由于笔者水平有线，对KMP算法的理解只是有限的。如想深入了解建议阅读KMP算法原文。

原理

首先，我们先确定模式串与目标串。模式串：较短的串。目标串：较长的串，被匹配的串。需要再目标串中找到模式串。
KMP算法的原理是在目标串与模式串每个字符的比较循环中，目标串的指针不回溯，通过修改模式串指针来加快匹配速度。那么重点就是怎么处理模式串来达到这个快速匹配。
处理模式串的原理是根据已匹配过的串得知相应的信息，本文最下方参考list中视频讲解对此有很好的解释，建议先看完视频再来看本文（视频只对原理和流程做了解释，但并未对如何求GetLPSArray做解释）。
我自己的理解是，在某个位置字符匹配错误，我们就能知道知道出错索引前的模式串与目标串的字符是相等的，在索引匹配前出错的字符串中如果有出现相同的串，那么就能跳过相同串的匹配来达到加速效果。请见如下例子

暴力匹配流程例子

0 1 2 3 4 5 6
目标串 a b a b a ? ?
模式串 a b a b c
0 1 2 3 4 5 6
目标串 a b a b a b ?
模式串 a b a b c
0 1 2 3 4 5 6
目标串 a b a b a b c
模式串 a b a b c

KMP算法流程

0 1 2 3 4 5 6
目标串 a b a b a ? ?
模式串 a b a b c
lps 0 0 1 2 0
0 1 2 3 4 5 6
目标串 a b a b a b c
模式串 a b a b c
lps 0 0 1 2 0

我们很容易理解暴力匹配的流程，这里比较难理解的是在 目标串[4]!=模式串[4]时，KMP算法直接将模式串的索引等于2，即目标串[4]开始与模式串[2]开始比较，目标串的索引不回溯。在这里我们能在大脑中轻松想到，在索引=4时，将模式串的索引变为2就能跳过多余的匹配，但要如何用算法描述这个过程请往下看。

GetLPSArray方法

现在重点就是求模式串所对应的lps数组。在上文代码中GetLPSArray方法已写出，现在来具体看看GetLPSArray方法的实现的原理。
敬请期待…

一些串对应的lps例子

例一

索引 0 1 2 3 4 5 6 7
模式串 a b c d a b c x
lps 0 0 0 0 1 2 3 0

例二

索引 0 1 2 3 4 5
模式串 a a b a a c
lps 0 1 0 1 2 0

例三

索引 0 1 2 3 4 5
模式串 a b a a b c
lps 0 0 1 1 2 0

例四

索引 0 1 2 3 4 5 6
模式串 a a c a a a c
lps 0 1 0 1 2 2 3

例五

索引 0 1 2 3 4 5 6 7
模式串 a a a c a a a a
lps 0 1 2 0 1 2 3 3

参考list