KMP 字符串匹配：只记一个状态转移

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

#include <bits/stdc++.h>
using namespace std;

vector<int> build_prefix_function(const string &pattern) {
    int m = (int)pattern.size();
    vector<int> pi(m + 1, 0);

    // Logical positions are 1..m; the string remains physically 0-indexed.
    auto P = [&](int i) -> char { return pattern[i - 1]; };

    // At the start of each iteration, j == pi[i - 1].
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && P(i) != P(j + 1)) {
            j = pi[j];
        }
        if (P(i) == P(j + 1)) j++;
        pi[i] = j;
    }

    return pi;
}

vector<int> kmp_match(const string &text, const string &pattern) {
    vector<int> positions;
    int n = (int)text.size();
    int m = (int)pattern.size();

    if (m == 0) return positions;

    vector<int> pi = build_prefix_function(pattern);
    auto T = [&](int i) -> char { return text[i - 1]; };
    auto P = [&](int i) -> char { return pattern[i - 1]; };

    for (int i = 1, j = 0; i <= n; i++) {
        while (j > 0 && T(i) != P(j + 1)) {
            j = pi[j];
        }
        if (T(i) == P(j + 1)) j++;

        if (j == m) {
            positions.push_back(i - m + 1); // 1-indexed match position
            j = pi[j];                      // Keep overlaps available
        }
    }

    return positions;
}

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

# KMP：build_prefix_function 返回 1-based 的 pi 数组（长度 m+1，pi[0] 占位不用）。
# kmp_match 返回 pattern 在 text 中所有出现位置的 1-based 起始下标
# （注意与 brute_force_match 的 0-based 约定不同）；空模式返回空列表。
# 预处理 O(m) + 匹配 O(n)，文本指针只前进不回溯。

Pi = list[int]  # 前缀函数，长度 m+1，pi[1..m] 有效，pi[0] 占位
Positions = list[int]  # 匹配起点列表，1-based


def build_prefix_function(pattern: str) -> Pi:
    """pi[i] = pattern[1..i] 的最长相等真前后缀长度；i 是 1-based 逻辑下标。"""
    m = len(pattern)
    pi = [0] * (m + 1)  # pi[1] = 0 天然成立，循环从 i = 2 开始
    j = 0  # 不变量：每轮开始时 j == pi[i - 1]
    for i in range(2, m + 1):
        # 失配就沿 pi 回退，直到能接上或退到 0；pattern[j] 是待比较的下一位。
        while j > 0 and pattern[i - 1] != pattern[j]:
            j = pi[j]
        if pattern[i - 1] == pattern[j]:
            j += 1
        pi[i] = j
    return pi


def kmp_match(text: str, pattern: str) -> Positions:
    """返回所有匹配起点（1-based）；同一位置可重叠，例如 text=aaa pattern=aa 返回 [1, 2]。"""
    positions: Positions = []
    n = len(text)
    m = len(pattern)

    if m == 0:
        return positions

    pi = build_prefix_function(pattern)
    j = 0  # 当前已匹配的 pattern 前缀长度
    for i in range(1, n + 1):
        while j > 0 and text[i - 1] != pattern[j]:
            j = pi[j]
        if text[i - 1] == pattern[j]:
            j += 1

        if j == m:
            positions.append(i - m + 1)  # 换算成 1-based 起点
            j = pi[j]  # 回退以保留重叠匹配，不能直接清零
    return positions

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

#include <bits/stdc++.h>
using namespace std;

vector<int> build_prefix_function(const string &pattern) {
    int m = (int)pattern.size();
    vector<int> pi(m + 1, 0);

    auto P = [&](int i) -> char { return pattern[i - 1]; };

    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && P(i) != P(j + 1)) {
            j = pi[j];
        }
        if (P(i) == P(j + 1)) j++;
        pi[i] = j;
    }

    return pi;
}

vector<int> kmp_match(const string &text, const string &pattern) {
    vector<int> positions;
    int n = (int)text.size();
    int m = (int)pattern.size();

    if (m == 0) return positions;

    vector<int> pi = build_prefix_function(pattern);
    auto T = [&](int i) -> char { return text[i - 1]; };
    auto P = [&](int i) -> char { return pattern[i - 1]; };

    for (int i = 1, j = 0; i <= n; i++) {
        while (j > 0 && T(i) != P(j + 1)) {
            j = pi[j];
        }
        if (T(i) == P(j + 1)) j++;

        if (j == m) {
            positions.push_back(i - m + 1);
            j = pi[j];
        }
    }

    return positions;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;

    vector<int> positions = kmp_match(text, pattern);
    if (positions.empty()) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 0; i < (int)positions.size(); i++) {
        if (i) cout << ' ';
        cout << positions[i];
    }
    cout << '\n';

    return 0;
}

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

# KMP：读入 text pattern（空白分隔），输出所有匹配起点（1 下标，空格分隔），
# 无匹配输出 -1。pi[i] 为 P[0..i] 的最长 border 长度（0 下标实现，语义同 C++ 的 1 下标版）。
import sys


def build_prefix_function(pattern: str) -> list[int]:
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi


def kmp_match(text: str, pattern: str) -> list[int]:
    positions: list[int] = []
    n, m = len(text), len(pattern)
    if m == 0:
        return positions

    pi = build_prefix_function(pattern)
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            positions.append(i - m + 2)  # i 是 0 下标末字符，起点换成 1 下标
            j = pi[j - 1]
    return positions


def main() -> None:
    data = sys.stdin.buffer.read().split()
    text = data[0].decode()
    pattern = data[1].decode()

    positions = kmp_match(text, pattern)
    if not positions:
        print(-1)
        return
    print(" ".join(map(str, positions)))


if __name__ == "__main__":
    main()