1.題目

農夫約翰出門沿著馬路散步，但是他現在發現自己可能迷路了！

沿路有一排共 $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

2.基本思想

二分 O(n2logn)

3.代碼實現

import java.util.*;public class _1460我在哪 {static String s;static int n;private static boolean check(int mid) {ArrayList<String> list = new ArrayList<>();for (int i = 0; i + mid - 1 <= n - 1; i++) {//從0開始枚舉長度為 mid的字符串String substring = s.substring(i,  i+mid);if (list.contains(substring)) return false;list.add(substring);}return true;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();s = sc.next();int l = 1, r = n ;while (l < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}System.out.println(l);}
}