Minimal Period

Interview

Time limit6sMemory limit1024 MB

Summary

Given a string with one extra character inserted, find the shortest original block that repeats and then ends in a prefix of itself.

Level: Medium5 of 10
Topics: String, String matching
Solved: No attempts yet

Problem

Katniss's squad uses a unique cipher to send messages. A cipher is the message repeated some nonzero number of times, followed by a prefix (possibly empty) of the original message appended to the end. For example, hello can be encoded as hellohellohell, hellohellohe, or hellohellohello.

Katniss recently received an encrypted message and immediately saw that something was wrong. Apparently an error occurred during transmission and an extra character was added somewhere. Katniss wants to know what the original message was, but she cannot say that for sure yet, so she wants the minimal length of a message that could have been encoded. For example, if she receives abadbab, she can tell that the middle has an extra character d, and the minimal length of the encoded message is 2.

Input

A single line contains a non-empty string of lowercase Latin letters. Its length is at least 2 and at most $10^6$ .

Output

Print one line containing the minimal length of the message that could have been encoded.

Examples3

Example 1
Input
```
abba
```
Expected output
```
2
```
Example 2
Input
```
abadbab
```
Expected output
```
2
```
Example 3
Input
```
daaa
```
Expected output
```
1
```