Shortest repeating motif

Write codeHard35 min

Your task

A sign controller paints a banner into a strip of cells by writing one motif into the strip over and over. Each write lays the motif down at a cell offset the controller picks. Writes may overlap as long as the overlapping cells agree, no write may run past either end of the strip, and every cell must be written at least once. Given the finished banner, return the length of the shortest motif that could have produced it. Every banner is produced by writing itself once, so the answer never exceeds the banner length. The empty banner needs no writes at all, so return 0. Overlap is the point: ababa comes from writing aba at offsets 0 and 2, so its answer is 3 even though ababa is not built by laying whole copies end to end.

Examples

shortest_cover_len(banner: str) -> int
Example 1
Inputshortest_cover_len("ababa")
Output3
Example 2
Inputshortest_cover_len("aabaa")
Output5
Example 3
Inputshortest_cover_len("abcabcabc")
Output3