枚举要观察的长度 K，只要所有长度为 K 的连续子串都互不相同，这个 K 就能唯一定位当前位置。
OJ: luogu
题目 ID: P5832
难度:普及-
标签:字符串枚举模拟
日期: 2026-06-19 09:44
同题版本
本题对应的 USACO 版本及解析：
思路
最直接的想法，就是把 K 从小到大枚举出来，然后检查所有长度为 K 的连续子串有没有重复。
这个最朴素、最容易理解的版本如下：
cpp
// brute.cpp：直接枚举 K，并暴力检查所有长度为 K 的子串是否互不相同。
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
bool check(int len) {
for (int i = 0; i + len - 1 < n; i++) {
for (int j = i + 1; j + len - 1 < n; j++) {
bool same = true;
for (int k = 0; k < len; k++) {
if (s[i + k] != s[j + k]) {
same = false;
break;
}
}
if (same) {
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 (check(len)) {
cout << len << '\n';
return 0;
}
}
return 0;
}为什么只需要检查“有没有重复子串”
如果某两个位置的长度为 K 的子串完全一样，那么 Farmer John 看到这一段颜色后，就没法分辨自己是在这两个位置中的哪一个。
反过来，如果所有长度为 K 的子串都不相同，那么每一段颜色都只会出现一次，他就能唯一定位。
所以题目等价于：
找到最小的 K，使得所有长度为 K 的连续子串互不相同。
如何检查一个固定的 K
固定长度 K 后，顺序取出所有子串：
s[0..K-1]s[1..K]s[2..K+1]- …
把它们放进一个集合里：
- 如果某个子串已经出现过，说明这个
K不行； - 如果全部都没有重复，说明这个
K可行。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
bool check(int len) {
set<string> st;
for (int i = 0; i + len - 1 < n; i++) {
string sub = s.substr(i, len);
if (st.count(sub)) {
return false;
}
st.insert(sub);
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
for (int len = 1; len <= n; len++) {
if (check(len)) {
cout << len << '\n';
return 0;
}
}
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
虽然可以继续优化，但这里 N <= 100，这个复杂度已经完全足够。
总结
这题的核心不是构造，而是把“唯一定位”翻译成“同长度子串不能重复”。
一旦看清这一点，直接枚举 K 并检查重复子串即可。