题目

农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！

沿路有一排共 N 个农场。

不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。

然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。

某些邮箱可能会有相同的颜色。

约翰想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。

例如，假设沿路的邮箱序列为 ABCDABC 。

约翰不能令 K=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。

最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。

输入格式

输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z 之内。

输出格式

输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 K 值。

数据范围

1≤N≤100

输入样例：

1
2
7
ABCDABC

输出样例：

1
4

解题思路

暴力枚举

可以看到，这道题的数据范围比较小，可以暴力枚举过关。根据题目意思，翻译过来就是从原字符串任意位置开始的长度为 i 的子字符串，在原字符串中都也找不到同样长度为 i 的子字符串了。

所以用一个哈希集合存储已经出现过的子字符串。如果对于相同长度的子字符串，已经在哈希集合中存在过了，说明此时的 i 不是正确答案。直接看代码理解吧：

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
#include <iostream>
#include <cstring>
#include <unordered_set>

using namespace std;

int n;
string str;

int main() {
    cin >> n >> str;
    unordered_set<string> st;
    for (int i = 1; i <= n; ++i) { // 子串长度
        int j = 0; 
        for (j; j + i <= n; ++j) { // 子串开头位置
            string sub = str.substr(j, i);
            if (st.count(sub) != 0) break;
            st.emplace(sub);
        }
        if (j + i == n + 1) { // 数组正常遍历结束，没有重复的
            cout << i << endl;
            break;
        }
    }
}

二分查找

二分查找相当于是一种优化，但是其实也没有太优。

这里的二分查找思路是二分查找最小的子串长度，代码和上面的都是大差不差的。

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
#include <iostream>
#include <cstring>
#include <unordered_set>

using namespace std;

int n, l, r, mid;
string str;

int main() {
    cin >> n >> str;
    unordered_set<string> st;
    l = 1, r = n; // [ )
    while (l < r) {
        mid = l + (r - l) >> 1;
        int j = 0; 
        for (j; j + mid <= n; ++j) { // 子串开头位置
            string sub = str.substr(j, mid);
            if (st.count(sub) != 0) l = mid + 1;
            st.emplace(sub);
        }
        if (j + mid == n + 1) { // 数组正常遍历结束，没有重复的
            r = mid;
        }
    }
    cout << mid << endl;
}