AcWing
1460. 我在哪
二分 + unordered_set(hash).
使用二分需要满足二段性。假设答案为ans，对于l < ans，子字符串将有重复；对于r > ans，子字符串将没有重复。此处1 <= ans <= n，可以使用二分；
unordered_set是一种stl，基于hash表，元素不重复，用于做字符串hash. set/multiset/unordered_set的对比如下：
unordered_set的头文件是<unordered_set>；multiset的头文件是<set>.
在判断当前字符个数mid是否满足不重复时，判断子字符串是否在hash表中，并将当前的子字符串加入。二分 + unordered_set，总的时间复杂度为O(nlogn).
#include <bits/stdc++.h>
using namespace std;
// 二分(二段性)+unordered_set(hash)
int n;
string s;
bool check(int mid){
unordered_set<string> his;
for(int i = 0; i <= n - mid; i++){
string temp = s.substr(i, mid);
if(his.count(temp)) return false;
his.insert(temp);
}
return true;
}
int main(){
cin >> n >> s;
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(!check(mid)) l = mid + 1;
else r = mid;
}
cout << r << endl;
return 0;
}