Where Am I?

题意

给定一个长度为 N 的字符串 S，表示沿路邮箱颜色。

要求找到最小的 K，使得任意长度为 K 的连续子串都能唯一确定它在字符串中的位置。

换句话说，所有长度为 K 的子串必须互不相同。

思路

朴素判断

对固定的 K，可以枚举任意两个起点，直接比较两个长度为 K 的子串是否相等：

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/**
 * 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-07-11 14:40
 * update_at: 2026-07-11 14:41
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

bool valid_len(int len) {
    // 朴素检查：枚举两段长度为 len 的子串，看是否相同。
    for (int i = 0; i + len <= n; i++) {
        for (int j = i + 1; j + len <= n; j++) {
            if (s.substr(i, len) == s.substr(j, len)) {
                return false;
            }
        }
    }
    return true;
}

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

    cin >> n >> s;

    for (int len = 1; len <= n; len++) {
        if (valid_len(len)) {
            cout << len << '\n';
            return 0;
        }
    }

    return 0;
}

如果存在两个相同子串，说明这个 K 不可行。

用集合判重

正式代码从小到大枚举 K。

对每个 K，把所有长度为 K 的子串放进集合 seen：

如果插入前发现这个子串已经出现过，说明 K 不可行；
如果所有子串都没有重复，说明 K 可行。

因为从小到大枚举，所以第一个可行的 K 就是答案。

代码

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/**
 * 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-07-11 14:40
 * update_at: 2026-07-11 14:41
 */
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

bool has_duplicate(int len) {
    set<string> seen;

    for (int i = 0; i + len <= n; i++) {
        string sub = s.substr(i, len);
        if (seen.count(sub)) {
            return true;
        }
        seen.insert(sub);
    }

    return false;
}

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

    cin >> n >> s;

    for (int len = 1; len <= n; len++) {
        if (!has_duplicate(len)) {
            cout << len << '\n';
            return 0;
        }
    }

    return 0;
}

复杂度

枚举长度、起点并构造子串，时间复杂度约为 $O(N^3 \log N)$ 。

集合中最多保存 $O(N)$ 个子串，空间复杂度为 $O(N^2)$ 。

总结

这题的关键是把“唯一确定位置”翻译成“同长度子串不能重复”。

然后从小到大枚举长度，做一次去重判断即可。

目录

题意

思路

朴素判断

用集合判重

代码

复杂度

总结