#236MediumString Matching· Prefix Function and Periods

Repeating Unit Finder

A telemetry device sends a heartbeat signature, a string made of lowercase letters. A healthy device repeats one short pattern over and over, so the signature is that pattern written `t` times for some `t >= 1`. Engineers want to read off the pattern. Return the **shortest** string `u` such that `s` equals `u` repeated `t` times for some integer `t >= 1`. If the signature is not a repetition of anything shorter, the shortest unit is the whole signature, so return `s` itself.

Input format

`s`: a non-empty string of lowercase letters.

Output format

A string: the shortest repeating unit.

Examples

Input: s = "abcabcabc"

Output: "abc"

Writing abc three times gives the signature, and no shorter unit does.

Input: s = "abaab"

Output: "abaab"

No proper block repeats to form abaab, so the unit is the whole string.

Input: s = "zzzz"

Output: "z"

The single letter z repeated four times is the signature.

Constraints

1 <= s.length <= 10^5
`s` contains only lowercase English letters.

#strings
#kmp
#prefix-function
#periodicity