接頭辞関数と周期の候補
長さLの各入力文字列sについて、接頭辞関数piを計算します。pi[i]はs[0..i]の接尾辞でもある最長の真の接頭辞の長さです。最後の値pi[L - 1]は、文字列全体で最長のボーダー（接頭辞かつ接尾辞）の長さを表します。このボーダーを除いた長さp = L - pi[L - 1]を周期の候補とします。
候補が実際の繰り返しブロックになるのは、Lがpで割り切れる場合だけです。そのとき文字列は同じブロックをちょうどL / p回繰り返しているため、答えはL / pです。割り切れない場合、文字列全体を均等に繰り返すより短いブロックはないので、答えは1です。1文字の文字列も同様に処理できます。接頭辞関数の値は0となり、p = 1、答えも1です。
入力は.だけの行が現れるまで処理します。入力が終わった場合もnullチェックによって安全に終了します。問題の有効な入力には終了記号が含まれます。終了記号以外の文字列は空ではないため、接頭辞関数の配列と最後の要素は必ず存在します。
接頭辞関数の計算は、各文字列について時間計算量O(L)、空間計算量O(L)です。
Java
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
33
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));
StringBuilder output = new StringBuilder();
String s;
while ((s = input.readLine()) != null && !s.equals(".")) {
output.append(repetitionCount(s)).append('\n');
}
System.out.print(output);
}
private static int repetitionCount(String s) {
int length = s.length();
int[] prefix = new int[length];
for (int i = 1, matched = 0; i < length; i++) {
while (matched > 0 && s.charAt(i) != s.charAt(matched)) {
matched = prefix[matched - 1];
}
if (s.charAt(i) == s.charAt(matched)) {
matched++;
prefix[i] = matched;
}
}
int period = length - prefix[length - 1];
return length % period == 0 ? length / period : 1;
}
}