【二分查找】我在哪？

题目

1460. 我在哪？ - AcWing题库

---

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

沿路有一排共 $N$ 个农场。

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

$1 \le N \le 100$

输入样例：

7
ABCDABC

输出样例：

4

解题

方法一：二分查找

思路

二分 $K$ 的最小值，二分成立的条件是：字符串中长度为 $K$ 的所有子串均不相同。

这题数据范围字符串长度只有 $100$ ，在写 check() 函数时可以直接遍历所有子串存入哈希表来判断是否有重复，如果数据范围再大点可以使用字符串哈希来优化检查子串的过程。

二分模板。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static String s;
    
    static boolean check(int m) {
        Set<String> st = new HashSet<>();
        for (int i = 0; i + m <= n; ++i) {
            if (!st.add(s.substring(i, i + m))) return false;
        }
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        s = in.readLine();
        int l = 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        System.out.println(l);
    }
}

字符串哈希优化：

import java.util.*;
import java.io.*;

public class Main {
    static final int P = 131;
    static int n;
    static long[] h, p;
    
    static boolean check(int m) {
        Set<Long> st = new HashSet<>();
        for (int i = 1; i + m - 1 <= n; ++i) {
            if (!st.add(subHash(i, i + m - 1))) return false;
        }
        return true;
    }
    
    static long subHash(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        char[] s = in.readLine().toCharArray();
        h = new long[n + 1];
        p = new long[n + 1];
        p[0] = 1L;
        for (int i = 1; i <= n; ++i) {
            h[i] = h[i - 1] * P + s[i - 1];
            p[i] = p[i - 1] * P;
        }
        int l = 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        System.out.println(l);
    }
}