二分

算法 > acwing 算法二分

发布时间 : 2022-04-10 22:57

字数:176 阅读 :

评论:

1460. 我在哪？

1460. 我在哪？

1460. 我在哪？

题目大意：

给一个字符串，问最小的k，使得长度大于k的子串两两不同

思路：

当k >= k_min,子串互不相同，所以存在二段性，可以用二分找到k_min

代码

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

using namespace std;

int n;
string str;

bool check(int mid)
{
    unordered_set<string> hash;

    for (int i = 0; i + mid - 1 < str.size(); i ++ )
    {
        auto s = str.substr(i, mid);
        if (hash.count(s)) return false;
        hash.insert(s);
    }

    return true;
}

int main()
{
    cin >> n;
    cin >> 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;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com