Find the Shortest Repeated Substring

You are given a string \(s_1\) that is formed by concatenating an unknown string \(s_2\) with itself repeatedly (at least twice). Your task is to determine the minimum possible length of \(s_2\).

In other words, find the smallest positive integer \(L\) such that \(s_1\) can be expressed as \(s_2\) repeated \(k\) times (where \(k \ge 2\)) with \(|s_2| = L\). Formally, if \(|s_1| = n\) and \(s_1 = s_2 s_2 \cdots s_2\) (\(k\) times), then determine the minimum \(L\) (with \(L \le n\)) that satisfies the condition.

Hint: You may consider using the prefix function (also known as the Knuth-Morris-Pratt failure function) to solve this problem efficiently. For a string of length \(n\) with prefix function \(\pi\), the answer will be \(n - \pi[n-1]\).

inputFormat

The input consists of a single line containing the string \(s_1\). It is guaranteed that \(s_1\) is composed by repeating some non-empty string \(s_2\) at least twice.

outputFormat

Output a single integer representing the minimum possible length of \(s_2\).

sample

abab

2