OJ/kmp.cpp at master · zgpio/OJ · GitHub

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cassert>
#include <cstring>
#include <iostream>

using std::cout;
using std::endl;

int *make_pmt(const char *p) // O(m)
{
    size_t len = strlen(p);
    int *ret = static_cast<int *>(malloc(sizeof(int) * len));
    assert(ret != nullptr);

    int ll = 0; // 原模式串的子串对应的前缀后缀的公共元素的最大长度

    // 第0个元素的ll值为0
    ret[0] = 0;

    for (size_t i = 1; i < len; ++i) {
        // 假设不成功时，再次尝试扩展
        while ((ll > 0) && (p[i] != p[ll])) {
            ll = ret[ll - 1];
        }

        // 对首尾字符或者扩展后的字符进行判断
        if (p[i] == p[ll]) {
            ++ll;
        }

        ret[i] = ll;
    }

    return ret;
}

int kmp(const char *s, const char *p) // O(m + n)
{
    int ret = -1;
    int sl = strlen(s);
    int pl = strlen(p);
    if (sl == 0 || pl == 0) return -1;
    int *pmt = make_pmt(p); // O(m)

    if ((0 < pl) && (pl <= sl)) {
        for (int i = 0, j = 0; i < sl; ++i) // O(n)
        {
            while ((j > 0) && (s[i] != p[j])) {
                j = pmt[j - 1]; // j = j - (j - LL) = LL = PMT[j-1];
            }

            if (s[i] == p[j]) {
                ++j;
            }

            if (j == pl) {
                ret = i + 1 - pl;
                break;
            }
        }
    }

    free(pmt);

    return ret;
}

int main()
{
    assert(kmp("abcde", "cde") == 2);
    assert(kmp("abcdecde", "cde") == 2);
    assert(kmp("abcde", "") == -1);
    assert(kmp("abcde", "a") == 0);
    assert(kmp("abcde", "bc") == 1);
    assert(kmp("BBC ABCDAB ABCDABCDABDE", "ABCDABD") == 15);
    // http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
    //   │B│B│C│ │A│B│C│D│A│B│ │A│B│C│D│A│B│C│D│A│B│D│E│
    // 1 │A│B│C│D│A│B│D│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
    // 2 │ │A│B│C│D│A│B│D│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
    // 3 │ │ │A│B│C│D│A│B│D│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
    // 4 │ │ │ │A│B│C│D│A│B│D│ │ │ │ │ │ │ │ │ │ │ │ │ │
    // 5 │ │ │ │ │A│B│C│D│A│B│D│ │ │ │ │ │ │ │ │ │ │ │ │
    // 6 │ │ │ │ │ │ │ │ │A│B│C│D│A│B│D│ │ │ │ │ │ │ │ │
    // 7 │ │ │ │ │ │ │ │ │ │ │A│B│C│D│A│B│D│ │ │ │ │ │ │
    // 8 │ │ │ │ │ │ │ │ │ │ │ │A│B│C│D│A│B│D│ │ │ │ │ │
    // 9 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │A│B│C│D│A│B│D│ │
    //
    // 部分匹配表(Partial Match Table), "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度.
    // │A│B│C│D│A│B│D│
    // │0│0│0│0│1│2│0│

    return 0;
}