Longest Periodic Substring

Given a non-empty string S consisting of lowercase English letters, find the length of the longest periodic substring. A substring is defined as periodic if it can be constructed by repeating a smaller substring multiple times, where the repetition occurs more than once. Formally, a substring T of S is periodic if there exists an integer k (1 ≤ k < |T|) such that T = Pⁿ (n > 1) for some substring P of length k.

If no periodic substring exists, output 0.

Example:

• Input: ababa, Output: 4
• Input: aaaaaa, Output: 6
• Input: abcdef, Output: 0

inputFormat

The input consists of a single line containing the string S. The string S contains only lowercase English letters.

outputFormat

Output a single integer representing the length of the longest periodic substring of S. If no such substring exists, output 0.## sample

ababa

4