Периоды всех префиксов строки

Дана строка s. Для КАЖДОГО префикса s[0..i] (i от 0 до len(s)-1) верните его наименьший период - длину такого p, что префикс можно получить повторением своих первых p символов (последнее повторение может быть неполным; для строки без нетривиального периода период равен её собственной длине). Результат - массив длины len(s), i-й элемент - период префикса длины i+1. Пересчитывать период каждого префикса заново - O(n^2). Префикс-функция (как в алгоритме КМП) даёт периоды всех префиксов за один проход O(n): период префикса длины L равен L - π[L-1].