BOJ. String square (4354)

On this page

Problem: BOJ 4354 — String Power

English · 한국어 · 日本語

Prefix function and the candidate period

For each input string s of length L, compute its prefix function pi. At position i, pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix. The last value pi[L - 1] gives the longest border of the whole string. Removing that border leaves a candidate period of length p = L - pi[L - 1].

The candidate is a true repeating block only when L is divisible by p. In that case the string consists of exactly L / p copies of the block. Otherwise, no shorter block repeats evenly across the entire string, so the answer is 1. This also handles a one-character string: its prefix-function value is 0, so p = 1 and the answer is 1.

Each input line is processed until the line containing only .. The null check also stops safely if input ends; valid problem input includes the terminator. Non-terminator strings are nonempty, so the prefix-function array and its final entry always exist.

The prefix function takes O(L) time and O(L) space per string.

Java

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;
    }
}