A period of a string s is a length p (1 <= p <= len(s)) such that s is a prefix of s[:p] repeated enough times. Equivalently, s[i] == s[i + p] for every valid i, or s[p:] == s[:len(s) - p]. The full length len(s) is always a period.
Write find_periods(s) -> list[int] returning all periods in increasing order.
find_periods("abcabca") # [3, 6, 7] ("abc" repeated gives "abcabca...")
find_periods("aaaa") # [1, 2, 3, 4]
find_periods("abcd") # [4]
Constraints: 1 <= len(s) <= 2·10^5. Checking each p by comparing s[p:] with the prefix is O(n²) in the worst case ("aaaa..."); aim for O(n) or O(n log n).
Show hint
You need to test "does the suffix starting at p equal a prefix of s?" for every p in O(1) each. Prefix hashes can do that, and so can a linear-time table of longest common prefixes between s and each of its suffixes.