Test

题意

求包含给定三个字符串作为子串的最短字符串长度。

思路

先说人话：只有 3 个串，顺序只有 $3!=6$ 种，枚举不是难点；真正的难点是把两个串之间的重叠用 KMP 在 $O(L)$ 内算出来——而 KMP 的 border 本来只认识"一个串自己"。

从两个串说起：重叠是什么

先退化到只有 A、B 两个串（保留机制的最简情形）：最短超串就是让 A 的后缀尽量叠进 B 的前缀，合并结果 = A + B[k:]，其中 $k$ = 满足"A 的后缀 = B 的前缀"的最大长度。

"后缀 = 前缀"正是 KMP 里 border 的定义——但 border 说的是同一个串的前缀等于后缀，这里却是 A 和 B 两个不同的串，一步跨不过去。

双串重叠：拼串降维成单串 border

解法是把两个串的关系压成一个串的性质：对 B + separator + A 求前缀函数。分隔符 \0 不在小写字母表里，border 不可能跨过它，所以整串的最长 border 恰好就是"B 的前缀 = A 的后缀"——最后一个 pi 值就是最大重叠 $k$ 。（代码用等价写法：把 right 当模式串在 left 上走一遍 KMP 自动机，扫描结束时的 j 就是重叠长度。）

这里"先判包含、再算重叠"的顺序很重要：如果 B 已经被 A 包含，直接取 A 即可；此时若先算重叠，KMP 的 j 会走满整个 B，结果就是错的。

三个串：枚举顺序 + 贪心为什么安全

固定顺序后每次取最大重叠叠加，6 种顺序全试一遍取最短。会不会担心"前两个串少叠一点，好让第三个串叠得更多"？不会：贪心合并后的串以 right 为前缀，所以它与下一个串的重叠只会 ≥ right 与下一个串的重叠——局部取最大重叠，全局不会变差（stays ahead）。

边界情形顺带检查：完全不同字母时重叠为 0，退化成普通拼接；一个串完全包含另一个串时，取较长者即可。

Python 知识

itertools.permutations(strings) 直接生成 6 种排列。
right in left 使用 Python 底层字符串搜索处理包含关系。
min(generator) 不需要保存所有候选超串。
bytes 可以直接拼接并用 b"\0" 作为安全分隔符。

代码

python

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
83import sys
from itertools import permutations


def build_prefix(s):
    """计算 KMP 前缀函数（border 数组）"""
    n = len(s)
    pi = [0] * n
    j = 0
    for i in range(1, n):
        # 沿 border 链回退，直到前缀可扩展或到根
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def get_overlap_concat(left, right):
    """
    求 left 后缀与 right 前缀的最长重叠长度 —— 版本1：拼串法。

    对 right + '#' + left 求前缀函数。'#' 不在字母表中，border 不能跨过它，
    所以整串的最长 border 恰好是 "right 的前缀 = left 的后缀"，
    最后一个 pi 值就是重叠长度。
    时间 O(|left|+|right|)，空间 O(|left|+|right|)（要存整串的 pi）。
    """
    pi = build_prefix(right + "#" + left)
    return pi[-1]


def get_overlap_automaton(left, right):
    """
    求 left 后缀与 right 前缀的最长重叠长度 —— 版本2：自动机游走法。

    把 right 当模式串，在 left 上走一遍 KMP 自动机，
    扫描结束时 j 就是最长重叠长度，与拼串法结果完全相同。
    时间 O(|left|+|right|)，空间 O(|right|)（只需存 right 的 pi）。
    调用前保证 right 不在 left 内部，所以 j 永远不会到达 len(right)。
    """
    if not right:
        return 0
    pi = build_prefix(right)
    j = 0  # KMP 自动机的当前状态 = 已匹配的 right 前缀长度
    for ch in left:
        while j > 0 and ch != right[j]:
            j = pi[j - 1]
        if ch == right[j]:
            j += 1
    return j


# 两种写法等价，二选一即可；这里用拼串法，与 index.md 的思路叙述一致
get_overlap = get_overlap_concat


def merge(left, right):
    """
    合并两个串：left 在前，right 在后，
    利用后缀-前缀重叠去掉重复部分，得到包含两者的最短串。
    """
    # 如果其中一个已经包含另一个，直接返回较长的
    if right in left:
        return left
    if left in right:
        return right
    overlap = get_overlap(left, right)
    return left + right[overlap:]


def solve():
    strings = sys.stdin.read().split()
    # 三串的合并顺序有 6 种排列，取最短结果
    answer = min(
        len(merge(merge(a, b), c))
        for a, b, c in permutations(strings)
    )
    print(answer)


if __name__ == "__main__":
    solve()

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-02
 * update_at: 2026-08-02
 */

/* CF25E Test */
/* 枚举 3! 种拼接顺序，每次把新串尽量重叠地接到当前串后面。
 * 重叠 = 左串后缀与右串前缀的最大公共长度，用 rbook 的前缀函数模板求解：
 * 对 right + '#' + left 求 pi，'#' 保证 border 不跨界，最后一位 pi 值即重叠。 */

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

// 前缀函数模板（原样取自 rbook 文章《KMP 字符串匹配》）
// pi[i]：pattern[0..i] 的最长相等真前后缀长度，pi[0] = 0
vector<int> build_prefix_function(const string &pattern) {
    int m = (int)pattern.size();
    vector<int> pi(m, 0);

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

    return pi;
}

// 返回 left 的后缀与 right 的前缀的最大重叠长度
int overlap(const string &left, const string &right) {
    // '#' 不在小写字母表中，整串 right#left 的 border 不可能跨过它，
    // 所以 border 长度 k 恰好满足：prefix(right, k) = suffix(left, k)
    string t = right + "#" + left;
    vector<int> pi = build_prefix_function(t);
    return pi.back();
}

// 判断 pattern 是否是 text 的子串（KMP 匹配，rbook 模板的匹配循环）
bool contains(const string &text, const string &pattern) {
    int m = (int)pattern.size();
    if (m == 0)
        return true;
    vector<int> pi = build_prefix_function(pattern);
    int j = 0; // 已匹配的模式串前缀长度
    for (char ch : text) {
        while (j > 0 && ch != pattern[j])
            j = pi[j - 1];
        if (ch == pattern[j])
            j++;
        if (j == m)
            return true; // 匹配完整
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s[3];
    cin >> s[0] >> s[1] >> s[2];

    int p[3] = {0, 1, 2};
    int ans = INT_MAX;
    do {
        string cur = s[p[0]];
        for (int i = 1; i < 3; i++) {
            const string &nxt = s[p[i]];
            if (contains(cur, nxt))
                continue;                        // nxt 已被 cur 包含
            if (contains(nxt, cur)) {            // cur 被 nxt 包含，直接替换
                cur = nxt;
                continue;
            }
            cur += nxt.substr(overlap(cur, nxt)); // 只拼上不重叠的部分
        }
        ans = min(ans, (int)cur.size());
    } while (next_permutation(p, p + 3));

    cout << ans << '\n';
    return 0;
}

教学对照版：只用 string::find 与 substr 比较、不用 KMP，重叠部分最坏 $O(L^2)$ ：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-02
 * update_at: 2026-08-02
 */

/* CF25E Test —— 教学对照版：只用 string::find 与 substr 比较，不用 KMP */
/* 与 main.cpp（KMP 版）对比可以看出：
 *   包含判断用 find 很直接；但重叠只能从大到小暴力试 k 再比较子串，
 *   最坏 O(L^2)（例如三个全是相同字符的串）。 */

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

// 返回 left 的后缀与 right 的前缀的最大重叠长度（暴力试 k）
int overlap(const string &left, const string &right) {
    int lim = min((int)left.size(), (int)right.size());
    for (int k = lim; k >= 1; k--)
        if (left.substr((int)left.size() - k) == right.substr(0, k))
            return k; // 从大到小第一个成功的 k 就是最大重叠
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s[3];
    cin >> s[0] >> s[1] >> s[2];

    int p[3] = {0, 1, 2};
    int ans = INT_MAX;
    do {
        string cur = s[p[0]];
        for (int i = 1; i < 3; i++) {
            const string &nxt = s[p[i]];
            if (cur.find(nxt) != string::npos)
                continue;                        // nxt 已被 cur 包含
            if (nxt.find(cur) != string::npos) { // cur 被 nxt 包含，直接替换
                cur = nxt;
                continue;
            }
            cur += nxt.substr(overlap(cur, nxt)); // 只拼上不重叠的部分
        }
        ans = min(ans, (int)cur.size());
    } while (next_permutation(p, p + 3));

    cout << ans << '\n';
    return 0;
}

复杂度

排列数为常数，每次合并线性，总时间 $O(|s_1|+|s_2|+|s_3|)$ ，辅助空间同阶。

总结

三个字符串时，枚举顺序比设计复杂状态更直接；KMP 则把最大重叠从平方比较降为线性。

目录

题意

思路

从两个串说起：重叠是什么

双串重叠：拼串降维成单串 border

三个串：枚举顺序 + 贪心为什么安全

Python 知识

代码

复杂度

总结