摘要
Title: 1460. 我在哪？
Tag: 字符串哈希、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

1460. 我在哪？

题意

农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共 N 个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A…Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A…Z 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
思路

题目大意是求最长相同的连续子串是多长，那么它最小是1，最长是假设是n，那么容易看出它具有二单调性，可以二分，二分后进行 $O(n)$ 的遍历，对比字符串是否相等可以用字符串哈希 $O(1)$ 比较，判断是否有字符串存在可以用哈希表 $O(1)$ 判断。最后答案加一

可以有两种二分
- 一种是求最大的连续子串，最后加一。这种向右二分
- 一种是求最小的不能连续的子串。这种向左二分
复杂度为 $O(nlogn)$

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-15 15:03:27
* @FilePath: \Acwing\1460\1460.cpp
* @LastEditTime: 2023-02-15 15:20:07
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

typedef unsigned long long ULL;
ULL p[N], h[N];
const int P = 13331;
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int n;
string s;

bool check(int x)
{
    unordered_map<int, int> st;
    for (int i = 1; i + x - 1 <= n; ++i)
    {
        int ss = get(i, i + x - 1);
        if (st.count(ss))
            return false;
        st[ss]++;
    }
    return true;
}

signed main()
{
    IOS;
    cin >> n >> s;
    s = " " + s;
    p[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i];
    }

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

'''
Author: NEFU AB-IN
Date: 2022-02-14 18:15:29
FilePath: \ACM\Acwing\1460.py
LastEditTime: 2022-02-14 20:16:51
'''

from collections import Counter

N = 155
P, MOD = 131, 1 << 64

p = [0] * N
h = [0] * N

p[0] = 1

d = Counter()


def get(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % MOD


def check(x):
    for i in range(1, n + 1):
        if i + x - 1 > n:
            break
        ss = get(i, i + x - 1)
        if d[ss]:
            return True
        d[ss] += 1
    return False


if __name__ == "__main__":
    n = int(input())
    s = input()

    s = " " + s
    for i in range(1, n + 1):
        p[i] = p[i - 1] * P % MOD
        h[i] = (h[i - 1] * P + ord(s[i])) % MOD

    l = 1
    r = n
    while l < r:
        mid = l + r + 1 >> 1
        if check(mid):
            l = mid
        else:
            r = mid - 1
    print(r + 1)

1460. 我在哪？

题意

思路

代码