Problem: BOJ 1305 — Advertisement · 한국어 · 日本語
Let the observed advertisement have length L. We need the shortest block whose infinite repetition begins with this entire observed string. Compute the KMP prefix function pi, where pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix. At the end, pi[L - 1] is the largest border of the whole string.
The border is exactly the portion that can overlap when one copy of the shortest block is followed by the next. Thus the shortest block length is L - pi[L - 1]. This is valid even when that length does not divide L: for example, ababa has a border of length 3, so repeating ab begins with ababa. With no nonempty border, the answer is L; if the string is a repetition of a smaller block, the formula returns that block’s length.
The input guarantees 1 <= L <= 1,000,000 and that the string contains exactly L characters. The implementation checks this before indexing the prefix array. Prefix-function construction and the final calculation take O(L) time; the prefix array uses O(L) space.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int length = Integer.parseInt(input.readLine());
String advertisement = input.readLine();
if (length <= 0 || advertisement == null || advertisement.length() != length) {
throw new IllegalArgumentException("Invalid advertisement length");
}
int[] pi = prefixFunction(advertisement);
System.out.println(length - pi[length - 1]);
}
private static int[] prefixFunction(String s) {
int[] pi = new int[s.length()];
int matched = 0;
for (int i = 1; i < s.length(); i++) {
while (matched > 0 && s.charAt(i) != s.charAt(matched)) {
matched = pi[matched - 1];
}
if (s.charAt(i) == s.charAt(matched)) {
pi[i] = ++matched;
}
}
return pi;
}
}