Ribbon Pattern Lengths
Hard · string matching
A jeweller threads coloured beads onto a ribbon one at a time. The ribbon is given as the string beads, with one lowercase letter per bead colour, in the order they were threaded.
Some ribbons are made by taking a short pattern of beads and repeating it over and over, stopping as soon as the ribbon is long enough. The last repeat may be cut short. For example, the pattern abc can make abcabca, and the pattern ab can make ababa.
After each bead is threaded, the jeweller wants to know how short the pattern could be. For every i from 1 to the length of beads, look at the first i beads and find the smallest length p such that those i beads are made by repeating the first p beads of the ribbon (a pattern of length i always works, since it needs no repeat).
Return a list of the lengths p, one per i, in order.
Examples
Example 1
Input: beads = "abaab"
Output: [1, 2, 2, 3, 3]
The first 4 beads, abaa, are the pattern aba cut short after one bead. The whole ribbon, abaab, is aba followed by ab.
Example 2
Input: beads = "aaaa"
Output: [1, 1, 1, 1]
Example 3
Input: beads = "abcabcab"
Output: [1, 2, 3, 3, 3, 3, 3, 3]
Constraints
- 1 <= len(beads) <= 10^5
- beads contains only lowercase English letters.