A necklace is a closed loop of beads, recorded as a string beads read clockwise from a marked bead (index 0). A jeweller cuts the loop just before bead k and lays the strand out, so it reads beads[k:] + beads[:k].
Return a sorted list of every cut position k (0 <= k < len(beads)) for which the laid-out strand reads the same forwards and backwards. Return [] if there is none.
Examples
Input: beads = "aab"
Output: [1]
Explanation: cutting before bead 1 gives "aba".
Input: beads = "abba"
Output: [0, 2]
Explanation: "abba" and "baab" are palindromes; "bbaa" and "aabb" are not.
Input: beads = "abab"
Output: []
Constraints
1 <= len(beads) <= 2 * 10**5, lowercase letters only.- Building and checking every rotation separately is far too slow for the longest loops.
Goals
- Rewrite 'this rotation is a palindrome' as 'the reversed string appears at a certain rotation'
- Find every rotation equal to a given string with one prefix-function scan of the doubled string
- Map each match back to the cut positions, including the two-solution case for even lengths