Cyclically Equivalent Prefix and Suffix

The problem involves strings comprised solely of lowercase English letters. Given a string \( S \) of length \( n \), you are tasked with finding the maximum integer \( L \) (with \( L \leq \frac{n}{2} \)) such that the prefix of \( S \) of length \( L \) and the suffix of \( S \) of length \( L \) are cyclically equivalent.

Two strings \( S_1 \) and \( S_2 \) (having equal length) are considered cyclically equivalent if one can be transformed into the other by taking some suffix of the string and moving it to the beginning. Equivalently, \( S_1 \) and \( S_2 \) are cyclically equivalent if and only if \( S_2 \) is a substring of \( S_1+S_1 \) (where \( + \) represents string concatenation).

Note that the empty string is both a prefix and a suffix for any string, and every string is cyclically equivalent to itself. However, since the prefix and suffix should not overlap, \( L \) is forced to be at most \( \frac{n}{2} \). Your goal is to maximize \( L \) satisfying the condition.

Example:

• For \( S = \texttt{abbaab} \) (with \( n = 6 \)), possible values of \( L \) are up to \( 3 \). Here, when \( L = 2 \), the prefix \( \texttt{ab} \) and the suffix \( \texttt{ab} \) are cyclically equivalent. However, for \( L = 3 \), the prefix \( \texttt{abb} \) and suffix \( \texttt{aab} \) are not cyclically equivalent. Thus, the answer is \( 2 \).

inputFormat

The input consists of a single line that contains the string \( S \). The string is non-empty and is composed of lowercase English letters.

outputFormat

Output a single integer: the maximum \( L \) (with \( L \leq \frac{n}{2} \)) such that the prefix of \( S \) of length \( L \) and the suffix of \( S \) of length \( L \) are cyclically equivalent.

sample

abbaab

2