P5832 [USACO19DEC] Where Am I? B

Farmer John goes out for a walk along the road, but now he realizes he might be lost. Along the road there is a line of $N$ farms. Unfortunately, the farms are not numbered, which makes it hard for Farmer John to tell where he is on this road. However, each farm has a colored mailbox by the roadside, so Farmer John hopes to uniquely determine his position by looking at the colors of the most recent few mailboxes. Each mailbox color is specified by a letter from A..Z, so the sequence of $N$ mailboxes along the road can be represented as a string of length $N$ consisting of letters A..Z. Some mailboxes may have the same color. Farmer John wants to know the smallest value of $K$ such that, by looking at any consecutive sequence of $K$ mailboxes, he can uniquely determine where this sequence occurs on the road. For example, suppose the mailbox sequence along the road is `ABCDABC`. Farmer John cannot set $K=3$, because if he sees `ABC`, there are two possible positions on the road where this consecutive color sequence could be. The smallest feasible value is $K=4$, because if he looks at any consecutive 4 mailboxes, that color sequence can uniquely determine his position on the road.

The first line of input contains $N$. The second line contains a string of $N$ characters, each of which is in A..Z.

Output one line containing an integer: the minimum value of $K$ that can solve Farmer John's problem.

Constraints: $1 \leq N \leq 100$。 Translated by ChatGPT 5