跳转至

KMP

模版
代码
C++
 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
vector<int> prefix(const string &str) {
    int len = str.size();
    vector<int> nxt(len);
    for (int i = 1 ; i < len ; i++) {
        int j = nxt[i - 1];
        while (j && str[i] != str[j]) {
            j = nxt[j - 1];
        }
        if (str[i] == str[j]) {
            j++;
        }
        nxt[i] = j;
    }
    return nxt;
}
vector<int> findOccurrences(const string &str, const string &x) {
    string cur = x + "#" + str;
    int len1 = str.size(), len2 = x.size();
    vector<int> nxt = prefix(cur);
    vector<int> pos;
    for (int i = len2 + 1 ; i <= len1 + len2 ; i++) {
        if (nxt[i] == len2) {
            pos.push_back(i - 2 * len2);
        }
    }
    return pos;
}
int match(const string &str, const string &x) {
    int cnt = 0;
    int len1 = str.size(), len2 = x.size();
    auto nxt = prefix(x);
    int j = 0;
    for (int i = 0 ; i < len1 ; i++) {
        while (j && str[i] != x[j]) {
            j = nxt[j - 1];
        }
        if (str[i] == x[j]) {
            j++;
        }
        if (j == len2) {
            return i - len2 + 1;
            j = nxt[j - 1];
        }
    }
    return -1;
}
代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
vector<int> prefix(const string &str) {
    int len = str.size();
    vector<int> nxt(len);
    for (int i = 2 ; i < len ; i++) {
        int j = nxt[i - 1];
        while (j && str[i] != str[j + 1]) {
            j = nxt[j];
        }
        if (str[i] == str[j + 1]) {
            j++;
        }
        nxt[i] = j;
    }
    return nxt;
}
例题

P3375 【模板】KMP - 洛谷

应用

字符串的周期

字符串的最小周期就是 \(len-nxt.back()\)

统计每个前缀出现的次数

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
string a;
cin >> a;
auto nxt = prefix(a);
int len = a.size();
vector<long long> ans(len + 1);
for (int i = 0 ; i < len ; i++) {
    ans[nxt[i]]++;
}
for (int i = len ; i >= 1 ; i--) {
    ans[nxt[i - 1]] += ans[i];
}
for (int i = 1 ; i <= len ; i++) {
    ans[i]++;
}
long long res = 0;
for (int i = 1 ; i <= len ; i++) {
    cout << i << " " << ans[i] << "\n";
}
例题

前缀函数 / KMP - QOJ.ac

#103. 子串查找 - LibreOJ