ACwing——我在哪？

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

沿路有一排共 N 个农场。

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

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

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

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

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

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

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

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

算法1-暴力枚举

找到长度最小的不重复子串即可

#include<iostream>

using namespace std;

int n;
string s;

int main()
{
    cin >> n >> s;
　　//k为子串的最大长度，找出满足条件k的最小值
    for(int k = 1;k <= n;k++)
    {
        bool flag = false;
　　　　//遍历是否存在相同的子串，如果不存在，即为答案
        for(int i = 0;i+k-1 < n;i++)
        {
            for(int j = i + 1;j + k -1 < n;j++)
            {
                bool same = true;
                for(int u = 0;u < k;u++)
                {
                    if (s[i+u] != s[j+u])
                    {
                        same = false;
                    }
                }
                if (same)
                {
                    flag = true;
                }
            }
            if (flag) break;
        }
        if (!flag)
        {
            cout << k << endl;
            break;
        }
    }
    return 0;
    
}

2.二分+哈希

利用stl中的unordered_set来实现查找是否存在相同子串

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

int n;
string str;
unordered_set<string> S;

bool check(int mid)
{
    S.clear();
    for (int i = 0; i + mid - 1 < n; i ++ )
    {
        string s = str.substr(i, mid);
        if (S.count(s)) return false;
        S.insert(s);
    }

    return true;
}

int main()
{
    cin >> n >> str;

    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << endl;

    return 0;
}